2017q1 Homework3 (software-pipelining)

contributed by<rayleigh0407>

前置作業

• 閱讀論文

1. INTRODUCTION
   • only relatively simple software prefetching algorithms have appeared in state-of-the-art compilers like icc [ICC] and gcc [GCC-4.0]
   • First, there are few rigorous guidelines on how best to insert prefetch intrinsics. Secondly, the complexity of the interaction between software and hardware prefetching is not well understood.
   • GHB hardware prefetcher & stream-based prefetcher
2. BACKGROUND ON SOFTWARE AND HARDWARE PREFETCHING
   • use stream prefetcher, GHB prefetcher, and content-based prefetcher as hardware-based prefetching mechanisms.
   • use x86 SSE extensions (_mm_prefetch)
   • Prefetching is useful only if prefetch requests are sent early enough to fully hide memory latency.
   • 預先取所需陣列位置+D後之值 D : prefetch distance
   • $$D\ge \lceil \frac{l}{s}\rceil$$
   • l : prefetch latency. s : 整個迴圈最短路徑.

抱歉沒能先整理好重點
– rayleigh0407

• 閱讀程式碼

_mm_loadu_si128

dst[127:0] := MEM[mem_addr+127:mem_addr]

_mm_unpacklo_epi32

INTERLEAVE_DWORDS(src1[127:0], src2[127:0]){ 
    dst[31:0]:= src1[31:0] 
    dst[63:32] := src2[31:0] 
    dst[95:64] := src1[63:32] 
    dst[127:96] := src2[63:32] 
    RETURN dst[127:0] 
} 

dst[127:0] := INTERLEAVE_DWORDS(a[127:0], b[127:0])

_mm_unpackhi_epi32

INTERLEAVE_HIGH_DWORDS(src1[127:0], src2[127:0]){
    dst[31:0] := src1[95:64]
    dst[63:32] := src2[95:64]
    dst[95:64] := src1[127:96]
    dst[127:96] := src2[127:96]
    RETURN dst[127:0] 
} 

dst[127:0] := INTERLEAVE_HIGH_DWORDS(a[127:0], b[127:0])

_mm_unpacklo_epi64

INTERLEAVE_QWORDS(src1[127:0], src2[127:0]){
    dst[63:0] := src1[63:0]
    dst[127:64] := src2[63:0]
    RETURN dst[127:0] 
} 

dst[127:0] := INTERLEAVE_QWORDS(a[127:0], b[127:0])

_mm_unpackhi_epi64

INTERLEAVE_HIGH_QWORDS(src1[127:0], src2[127:0]){ 
    dst[63:0] := src1[127:64]
    dst[127:64] := src2[127:64]
    RETURN dst[127:0] 
} 

dst[127:0] := INTERLEAVE_HIGH_QWORDS(a[127:0], b[127:0])

_mm_storeu_si128

MEM[mem_addr+127:mem_addr] := a[127:0]

藉由這些 SSE 運算工具, 可以得知轉置的過程如下

$$\begin{gathered} Step1:I=\left[\begin{array}{cccc}{0}_0& 0_1& 0_2& 1_1\\ 1_0& 1_1& 1_2& 1_3\\ 2_0& 2_1& 2_2& 2_3\\ 3_0& 3_1& 3_2& 3_3\end{array}\right] \\ Step2:T=\left[\begin{array}{cccc}{0}_0& 1_0& 0_1& 1_1\\ 2_0& 3_0& 2_1& 3_1\\ 0_2& 1_2& 0_3& 1_3\\ 2_2& 3_2& 2_3& 3_3\end{array}\right] \\ Step3:I=\left[\begin{array}{cccc}{0}_0& 1_0& 2_0& 3_0\\ 0_1& 1_1& 2_1& 3_1\\ 0_2& 1_2& 2_2& 3_2\\ 0_3& 1_3& 2_3& 3_3\end{array}\right] \end{gathered}$$