amzshar

2007年12月20日 星期四

.
====== Ch5.8 Main memory and Organization for improving performance (三種) ======
※ 1. Wider Main Memory : 若寬度變兩倍,存取記憶體只需原來的一半
※ 2. Simple Interleaved Memory : 簡單交錯式的記憶體
※ 3. Independent Memory Banks : 獨立式記憶體庫
====== Ch5.10 Virtual Memory ======
※ Virtual Memory (虛擬記憶體) :
1. A means of sharing a smaller amount of physical memory among many processes.
2. It divides physical memory into blocks and allocates them to different processes.
※ There are further differences between caches and virtual memory beyond those quantitative :
1. Replacement on cache misses is primarily controlled by hardware, while virtual memory replacement is primarily controlled by the operating system. The longer miss penalty means it’s more important to make a good decision, so the operating system can be involved and spend take time deciding what to replace.
2. The size of the processor address determines the size of virtual memory, but the cache size is independent of the processor address size.
3. In addition to acting as the lower-level backing store for main memory in the hierarchy, secondary storage is also used for the file system. In fact, the file system occupies most of secondary storage. It is not normally in the address space.

※ Translation lookaside buffer (TLB) 轉換後備緩衝區 :
- also called translation buffer (TB)
- It is special address translation cache.
- A TLB entry is like a chche entry where the tag holds portions of the virtual address and the data portion hold a physical page frame number, protection field, valid bit, and usually a use bit and dirty bit.

※ Selecting a Page Size : 分頁大小
=> The following favor a larger size:
1. The size of the page table is inversely proportional to the page size; memory (or other resources used for the memory map) can therefore be saved by making the pages bigger.
2. As mentioned on page 433 in section 5.7, a larger page size can allow larger caches with fast cache hit times.
3. Transferring larger pages to or from secondary storage, possibly over a network, is more efficient than transferring smaller pages.
4. The number of TLB entries are restricted, so a larger page size means that more memory can be mapped efficiently, thereby reducing the number of TLB misses.

====== Ch5.11 Protection and Examples of Virtual Memory ======
※Protecting Processes
The simplest protection mechanism is a pair of registers that checks every address to be sure that it falls between the two limits, traditionally called base and bound. An address is valid if
　　Base <= Address <= Bound
In some systems, the address is considered an unsigned number that is always added to the base, so the limit test is just
　　(Base + Address) <= Bound

※ the Computer Designer has 3 more responsibilities in helping the OS Designer protect processes from each other:
1. Provide at least two modes, indicating whether the running process is a user process or an operating system process. This latter process is sometimes called a kernel process, a supervisor process, or an executive process.
2. Provide a portion of the CPU state that a user process can use but not write. This state includes the base/bound registers, a user/supervisor mode bit(s), and the exception enable/disable bit. Users are prevented from writing this state because the operating system cannot control user processes if users can change the address range checks, give themselves supervisor privileges, or disable exceptions.
3. Provide mechanisms whereby the CPU can go from user mode to supervisor mode and vice versa. The first direction is typically accomplished by a system call, implemented as a special instruction that transfers control to a dedicated location in supervisor code space. The PC is saved from the point of the system call, and the CPU is placed in supervisor mode. The return to user mode is like a subroutine return that restores the previous user/supervisor mode.

End.

2007年12月20日 星期四

2007年12月20日 星期四

.
====== Ch5.5 Reducing Miss Rate (也是五種) ======
※ 3種Miss Type(失誤類型)：
1. Compulsory—The very first access to a block cannot be in the cache, so the block must be brought into the cache. These are also called cold start misses or first reference misses.
2. Capacity—If the cache cannot contain all the blocks needed during execution of a program, capacity misses (in addition to compulsory misses) will occur because of blocks being discarded and later retrieved.
3. Conflict—If the block placement strategy is set associative or direct mapped, conflict misses (in addition to compulsory and capacity misses) will occur because a block may be discarded and later retrieved if too many blocks map to its set. These misses are also called collision misses or interference misses. The idea is that hits in a fully associative cache which become misses in an N-way set associative cache are due to more than N requests on some popular sets.
※ <方法1.> Larger Block Size :
較大區塊利用空間區域性來減低失誤率(減低Compulsory Miss),但增加penalty,與Conflict Miss.
※ <方法2.> Larger Cache :
減低Capacity Miss, 但是會有較長的Hit time,及較高成本.
※ <方法3.> Higher Associativity :
2:1 cache rule of thumb : a direct-mapped cache of size N has about the same miss rate as a 2-way set associative cache of size N/2. This held for cache sizes less than 128 KB.
※ <方法4.> Way Prediction & Pseudo-Associative Caches :
只檢查快取記憶體中的一部份來看是否命中,若失誤,再檢查其他部分, (減低Conflict Miss, )
In way-prediction, extra bits are kept in the cache to predict the set of the next cache access. This prediction means the multiplexor is set early to select the desired set, and only a single tag comparison is performed that clock cycle. A miss results in checking the other sets for matches in subsequent clock cycles.
pseudo-associative or column associative. Accesses proceed just as in the direct-mapped cache for a hit. On a miss, however, before going to the next lower level of the memory hierarchy, a second cache entry is checked to see if it matches there. A simple way is to invert the most significant bit of the index field to find the other block in the “pseudo set.”
※ <方法5.> Compiler Optimization :
1. Loop Interchange :

/* Before */
　for (j = 0; j < 100; j = j+1)
　　for (i = 0; i < 5000; i = i+1)
　　　x[i][j] = 2 * x[i][j];

/* After */
　for (i = 0; i < 5000; i = i+1)
　　for (j = 0; j < 100; j = j+1)
　　　x[i][j] = 2 * x[i][j];

2. Blocking :

/* Before */
　for (i = 0; i < N; i = i+1)
　　for (j = 0; j < N; j = j+1)　
　　　{　r = 0;
　　　　　for (k = 0; k < N; k = k + 1)
　　　　　　r = r + y[i][k]*z[k][j];
　　　　　　x[i][j] = r;
　　　};

/* After */
　for (jj = 0; jj < N; jj = jj+B)
　　for (kk = 0; kk < N; kk = kk+B)
　　　for (i = 0; i < N; i = i+1)
　　　　for (j = jj; j < min(jj+B,N); j = j+1)
　　　　　{　r = 0;
　　　　　　　for (k = kk; k < min(kk+B,N); k = k + 1)
　　　　　　　　r = r + y[i][k]*z[k][j];
　　　　　　　x[i][j] = x[i][j] + r;
　　　　　};

====== Ch5.6 Reducing Cache miss penalty or Miss rate via parallelism (三種) ======
※方法1☆ Nonblocking Caches to Reduce Stalls on Cache Misses (無阻隔式快取記憶體):
又稱 lockup-free cache (無鎖式快取記憶體)
1. Hit under miss optimization : Reduces the effective miss penalty by being helpful during miss instead of ignoring the requests of CPU.
2. Hit under multiple miss (or miss under miss) : It is beneficial only if the memory system can service multiple misses.
※方法2☆ Hardware prefetching of instructions and data :

※方法3☆ compiler-controlled prefetching :
1. an alternative to hardware prefetching is for the compiler to insert preftech instructions.
2. The most effective prefetch is “semantically invisible”to a program :
- It doesn’t change the contents of registers and memory, and
- It cannot cause virtual memory faults.

2007年12月19日 星期三

.
====== Ch5.4 Reducing Cache Miss Penalty (五種) ======
※ [方法1] Multi-Level Caches :

Average memory access time = Hit timeL1 + Miss rateL1 × Miss penaltyL1
and
Miss penaltyL1 = Hit timeL2 + Miss rateL2 × Miss penaltyL2

所以

Average memory access time
= Hit timeL1 + Miss rateL1× (Hit timeL2 + Miss rateL2 × Miss penaltyL2)

1. Local miss rate : This rate is simply the number of misses in a cache divided by the total number of memory accesses to this cache. As you would expect, for the first-level cache it is equal to Miss rate L1 and for the second-level cache it is Miss rate L2.
2. Global miss rate : The number of misses in the cache divided by the total number of memory accesses generated by the CPU. Using the terms above, the global miss rate for the first-level cache is still just Miss rateL1 but for the second-level cache it is Miss rate L1 × Miss rate L2.

Average memory stalls per instruction
= Misses per instruction L1× Hit time L2 + Misses per instruction L2 × Miss penalty L2.

EXAMPLE Suppose that in 1000 memory references there are 40 misses in the 1st-level cache and 20 misses in the 2nd-level cache. What are the various miss rates? Assume the Miss penalty from L2 cache to Memory is 100 clock cycles, the Hit time of L2 cache is 10 clock cycles, the Hit time of L1 is 1 clock cycles, and there are 1.5 memory references per instruction. What is the average memory access time and average stall cycles per instruction? Ignore the impact of writes.
ANSWER :
1st-level local and global miss rate = 40 / 1000 = 4%
2nd-level local miss rate = 20 / 40 = 50%
2nd-level global miss rate = 20 / 1000 = 2%
=>
Average memory access time
　= 1 + 4%(10 + 50% × 100 ) = 3.4 clock cycles.
(若無L2 => Average memory access time = 1 + 4% × 100 = 5 clock cycles.)
1.5 memory references per instruction => 1000 memory reference per 667 instructions.
所以 每千個指令的失誤率 Miss Rate L1 = 40*1.5 = 60 , Miss Rate L2 = 20*1.5=30
Average memory stalls per instruction
= Misses per instruction L1× Hit time L2 + Misses per instruction L2 × Miss penalty L2
= (60/1000) × 10 + (30/1000) × 100
= 0.060 × 10 + 0.030 × 100 = 3.6 clock cycles

另一種算法是 (Average memory access time - L1 Hit time ) × 平均Cache存取次數
= (3.4 – 1.0) * 1.5 = 3.6 clock cycles.
※ [方法2] Critical word first & Early restart : (只對Block大的Cache有效)
1. Critical word first : Request the missed word first from memory and send it to the CPU as soon as it arrives; let the CPU continue execution while filling the rest of the words in the block. Critical-word-first fetch is also called wrapped fetch and requested word first.
2. Early restart : Fetch the words in normal order, but as soon as the requested word of the block arrives, send it to the CPU and let the CPU continue execution.
※ [方法3] Giving Priority to Read Misses over Writes :
This optimization serves reads before writes have been completed.
※ [方法4] Merging write buffer : (將連續字元組的多個寫入動作合併為單一區塊)
If the buffer contains other modified blocks, the addresses can be checked to see if the address of this new data matches the address of the valid write buffer entry. If so, the new data are combined with that entry,
called write merging.
※ [方法5] Victim caches :
One approach to lower miss penalty is to remember what was discarded in case it is needed again. Since the discarded data has already been fetched, it can be used again at small cost.

2007年12月19日 星期三
.
====== Ch5.3 Cache Performance ======
※
※ Average Memory Access Time (AMAT) = Hit time + Miss Rate × Miss Penalty
※
EXAMPLE : 比較何者有較低的失誤率,
(假設Cahe為具有寫入緩衝區的直接寫入式cache)
1. 16KB指令快取 + 16KB資料快取,
2. 32KB合併式快取(Unified Cache),
假設36%指令是資料快取, 而命中需1個時脈週期(Hit time=1),
失誤代價=100時脈週期(Miss Penalty=100).
而Unified合併式快取,因無法同時處理兩個要求,Load與Store必須多出額外的1個時脈週期.

ANSWER :
先計算每千個指令的失誤次數轉換為失誤率.
Misses / Instruction = ( Miss Rate × Memory Access ) / Instruction

Miss Rate = [ ( Misses/1000 Instructions ) / 1000 ] / ( Memory Access / Instruction )

因為每個指令存取需要一次的 Memory Access以取得指令:
=> Miss Rate 16KB指令 = [ 3.82 / 1000 ] / 1.00 = 0.004 (佔 74%)
=> Miss Rate 16KB資料 = [ 40.9 / 1000 ] / 0.36 = 0.114 (佔26%)
=> 分離式Cache整體失誤率 = 74% × 0.004 + 26% × 0.114 = 0.0324
合併式Unified Cache必須計算指令與資料存取:
=> Miss Rate 32KB合併式
　　= [ 43.3 / 1000 ] / ( 1.00 + 0.36 ) = 0.0318 (比較上,稍微低)
Average memory access time (AMAT)
= % instructions × (Hit time + Instruction miss rate × Miss penalty) +% data × (Hit time + Data miss rate × Miss penalty)
=> AMAT分離式 = 74% × ( 1 + 0.004 × 100 ) + 26% × ( 1 + 0.114 × 100 ) = 4.24
=> AMAT合併式 = 74% × ( 1 + 0.0318 × 100 ) + 26% × ( 1 + 1 + 0.0318 × 100 ) = 4.44
所以, 分離式Cache在每個時脈週期提供兩個記憶體存取,
因而避免掉結構危障.
雖然Miss Rate 較高,但AMAT仍然比僅單一存取阜的Unified Cache要短.
※ 比較有沒有Cache對效能的影響
EXAMPLE : An in-order execution computer
(Such as Ultra SPARC III), Cache Penalty=100 clock cycles,
all instructions normally take 1.0 clock cycles,
Assume the Average Miss Rate is 2%, there is an average of 1.5 memory references per instruction, and that the average number of Cache Misses per 1000 instructions is 30.
What is the impact on performance when behavior of the cache is included?
Calculate the impact using both misses per instruction and miss rate.
ANSWER :
CPU time
= IC×[ ( CPI execution + (Memory stall clock cycles)/Instruction ] × Clock cycle time
1. 包含Cache失誤的效能---
CPU time = IC × (1.0 + 30/1000 × 100) × Clock cycle time
　　　　　= IC × 4.0 × Clock cycle time
2. 使用Miss Rate來計算---
CPU time = IC×[CPI execution + Miss Rate×(Memory accesses/Instruction)×Miss penalty]×Clock cycle time

=> CPU time
　= IC×[1.0 + 2%×1.5×100]×Clock cycle time
　　= IC × 4.0 × Clock cycle time
The clock cycle time and (IC) instruction count are the same, with or without a cache.
Thus, CPU time increases fourfold, with CPI from 1.00 for a “perfect cache” to 4.00 with a cache that can miss.
Without any memory hierarchy at all the CPI would increase again to 1.0 + 100 × 1.5 or 151— a factor of almost 40 times longer than a system with a cache!
※ 比較不同架構的Cache 對效能得影響 (Direct-Mapped v.s. 2-way-associative ):
EXAMPLE Assume that the CPI=2.0 with a perfect cache, the clock cycle time is 1.0 ns, there are 1.5 memory references per instruction, both caches size is 64 KB, and block size of 64 bytes. One cache is direct mapped and the other is two-way set associative. For set-associative caches we must add a multiplexor to select between the blocks in the set depending on the tag match. Since the speed of the CPU is tied directly to the speed of a cache hit, assume the CPU clock cycle time must be stretched 1.25 times to accommodate the selection multiplexor of the set-associative cache. Cache miss penalty=75 ns for either cache organization. First, calculate the average memory access time, and then CPU performance. Assume the hit time=1 clock cycle, the Miss Rate = 1.4% for direct-mapped 64-KB cache, the Miss Rate=1.0% for a two-way set-associative cache.
ANSWER :
Average memory access time = Hit time + Miss rate × Miss penalty

AMAT(1-way) = 1.0 + (0.014×75) = 2.05 ns
AMAT(2-way) = 1.0×1.25 + (0.01×75) = 2.00 ns (AMAT較佳)
CPU time = IC×[CPI execution + Miss Rate×(Memory accesses/Instruction)×Miss penalty]×Clock cycle time
CPU time(1-way) = IC×[2 + 0.0014×1.5×75]×1.0 = 3.58 × IC (CPU time較佳)
CPU time(2-way) = IC×[2×1.25 + 0.01×1.5×75] ×1.0=3.63 × IC
=> 相對效能 = CPU time (2-way) / CPU time(1-way) = 3.63 / 3.58 = 1.01
※ Out-of-Order Execution Processor:
( Memory stall cycles / Instruction )
= ( Misses / Instruction ) * (Total miss latency – Overlapped miss latency )

2007年12月19日 星期三
.
※ Q1. Where can a block be placed in a cache?
1. If each block has only one place it can appear in the cache, the cache is said to be direct mapped.
This mapping is usually : (Block address) MOD (Number of blocks in cache)
2. If a block can be placed anywhere in the cache, the cache is said to be fully associative.
3. If a block can be placed in a restricted set of places in the cache, the cache is set associative.
A set is a group of blocks in the cache. A block is first mapped onto a set, and then the block can be placed anywhere within that set. The set is usually chosen by bit selection;
that is, (Block address) MOD (Number of sets in cache)

If there are n blocks in a set, the cache placement is called n-way set associative.

※ Q2: How is a block found if it is in the cache?
1. offset從區塊選出需要的資料,
2. Index field選出某一集合,
3. Tag field比對是否命中

如果Cache大小不變,增加關連性會增加每個集合中的區塊數,=>Index會縮短,Tag會加長.
Index=0即為Full associative.
※ Q3: Which block should be replaced on a cache miss?
1. Random
2. LRU(least-recently used)
3. FIFO
※ Q4: What happens on a write?
1. Write through : The information is written to both the block in the cache and to the block in the lower-level memory.
2. Write back : The information is written only to the block in the cache. The modified cache block is written to main memory only when it is replaced.
To reduce the frequency of writing back blocks on replacement, a feature called the dirty bit is commonly used. This status bit indicates whether the block is dirty (modified while in the cache) or clean (not modified). If it is clean, the block is not written back on a miss, since identical information to the cache is found in lower levels.
※ When the CPU must wait for writes to complete during write through, the CPU is said to write stall. A common optimization to reduce write stalls is a write buffer, which allows the processor to continue as soon as the data is written to the buffer, thereby overlapping processor execution with memory updating. As we shall see shortly, write stalls can occur even with write buffers.
Since the data are not needed on a write, there are two are two options on a write miss:
1. Write allocate : The block is allocated on a write miss, followed by the write hit actions above. In this natural option, write misses act like read misses.
2. No-write allocate : This apparently unusual alternative is write misses do not affect the cache. Instead, the block is modified only in the lower level memory.
※ Alpha 21264 Data Cache :
Cache Size = 64K bytes = 2^16 bytes.
Block Size = 64 bytes = 2^6 bytes. (block offset = 6)
2-way associativity. Write-back and Write-allocate.
2^index = Cache Size / (Block Size × Set associativity)
2^index = 65526 / (64 × 2) => index = 512 => index field = 9 bits
步驟1 : 21264CPU送出48 bits虛擬位址到Cache以供Tag檢查,並在同一時間將虛擬位址轉換為44 bits的實際位址. => Tag field = 44 -9 -6 = 29 bits
步驟2 : Index選擇,兩個Tag同時被比較,而比較結果相同者被選出,
步驟3 : 兩個標籤被由Cache讀出後,就與由CPU送出的區塊位址中的標籤部分比較.為了確定該標籤包含有效資訊, Valid bit必須為1,否則比較的結果就會被忽略.
步驟4 : 假設其中一個標籤比對符合,就會通知CPU利用比對成功的輸入從2:1Mux載入適當資料.
21264採用Write-back方法,並對每一block利用一個Dirty Bit來記錄其是否曾被寫入.如果該要被置換出的Block (Victim) 曾被修改過,它的資料以及位址就會被送進 Victim buffer.
CPU知道送出的是Instruction Address或Data address,所以不同類型的Address可以使用不同的port.如此可以將記憶體架構與CPU間的頻寬加倍. 分離式Cache也讓設計者可以針對每個Cache做最佳化(不同的容量、區塊大小、關連性都可調整). 而另一種 Unified Cache or mixed Cache are applied to caches that can contain either instructions or data.

2007年12月19日 星期三

2007年12月18日 星期二

=== Ch4.5 Hardware Support for Exposing more parallelism at compile time ===
※ such as loop unrolling, software pipelining, and trace scheduling can be used to increase the amount of parallelism available when the behavior of branches is fairly predictable at compile time. When the behavior of branches is not well known, compiler techniques alone may not be able to uncover much ILP.
※ 將指令擴充 :
The first is an extension of the instruction set to include conditional (條件指令) or predicated (預測指令) instructions.
※ 條件指令(Conditional instructions) :
1. An instruction refers to a condition, which is evaluated as part of the instruction execution.
2. If the condition is true, the instruction is executed normally.
3. If the condition is false, the execution continues as if the instruction were no-op (空指令).
例如: if (A==0) {S=T;}
※ Compiler Speculation with Hardware Support :
To speculate ambitiously requires 3 capabilities: (良好的預測執行3要素)
1. the ability of the compiler to find instructions that, with the possible use of register renaming, can be speculatively moved and not affect the program data flow,
2. the ability to ignore exceptions in speculated instructions, until we know that such exceptions should really occur, and
3. the ability to speculatively interchange loads and stores, or stores and stores, which may have address conflicts.
※ Hardware Support for Preserving Exception Behavior :
There are 4 methods that have been investigated for supporting more ambitious speculation without introducing erroneous exception behavior:
1. The H/W and OS cooperatively ignore exceptions for speculative instructions.
　- this approach preserves exception behavior for correct programs, but not for incorrect ones.　 This approach may be viewed as unacceptable for some programs, but it has been used, under program control, as a “fast mode” in several processors.
2. Speculative instructions that never raise exceptions are used, and checks are introduced to determine when an exception should occur.
3. A set of status bits, called poison bits, are attached to the result registers written by speculated instructions when the instructions cause exceptions. The poison bits cause a fault when a normal instruction attempts to use the register.
4. A mechanism is provided to indicate that an instruction is speculative and the H/W buffers the instruction result until it is certain that the instruction is no longer speculative.
----------------------------------------------------------
Example1 : Here is an unusual loop. First, list the dependences and then rewrite the loop so that it is parallel.
　　for (i=1;i<100;i=i+1) {
　　　a[i] = b[i] + c[i];　　/* S1 */
　　　b[i] = a[i] + d[i];　　/* S2 */
　　　a[i+1] = a[i] + e[i];　/* S3 */
　　}
Solution :
1. S2 to S1以及 S3 to S1, a[] -> true-dep.
2. S1 to S2, bi -> anti-dep.
3. S3 to S1 loop-carried output-dep.
4. S3 to S2 loop-carried true-dep.
5. S3 to S3 loop-carried true-dep.
化解為：
　　for (i = 1; i < 100; i = i + 1) {
　　　　a[i] = b[i] + c[i]; //S1
　　　　b[i] = a[i] + d[i]; //S2
　　}
　　a[100] = a[99] + e[99];
----------------------------------------------------------
EXAMPLE2: Here is a simple code fragment:
　for (i=2;i<=100;i+=2)
　　　a[i] = a[50*i+1];
To use the GCD test, this loop must first be “normalized”—written so that the index starts at 1 and increments by 1 on every iteration. Write a normalized version of the loop (change the indices as needed), then use the GCD test to see if there is a dependence.
Solution :
normalized正規化 =>
　for(i<1 ; i<=50 ; i++) {
　　　a[2*i] = a[ (100*i) + 1 ];
　}
a=2, b=0, c=100, d=1 代入 GCD test
=> gcd(2,100)=2 且 d-b=1, 因為1是2的因數, 所以有相依性存在.
(但是,實際上,Loop 載入順序是 a[101], a[201], …,a[5001]並指到 a[2], a[4],…,a[100]並不是相依性)

2007年12月17日 星期

=== Ch4.4 Advanced Compiler Support for Exposing and Exploiting ILP ===
※ The analysis of loop-level parallelism focuses on determining whether data accesses in later iterations are dependent on data values produced in earlier iterations, such a dependence is called a loop-carried dependence.
程式範例：
　for (i=1; i<=100; i=i+1) {
　　A[i+1] = A[i] + C[i];　　/* S1 */
　　B[i+1] = B[i] + A[i+1];　/* S2 */
　}
--
A[2] = A[1] + C[1]
B[2] = B[1] + A[2]
--
A[3] = A[2] + C[2]
B[3] = B[2] + A[3]
--
... ... ...
--
A[101] = A[100] + C[100]
B[101] = B[100] + A[101]
--

※ Loop-carried dependence不見得會妨礙Parallelism:
程式範例：
　for (i=1; i<=100; i=i+1) {
　　A[i] = A[i] + B[i];　　　/* S1 */
　　B[i+1] = C[i] + D[i];　　/* S2 */ 　}
--
A[1] = A[1] + B[1]
B[2] = C[1] + D[2]
--
A[2] = A[2] + B[2]
B[3] = C[2] + D[2]
--
... ... ...
--
A[100] = A[100] + B[100]
B[101] = C[100] + D[100]
--
S1相依於S2,之間存在Loop-carried dependence.
轉換關鍵性：
1.S1到S2沒有相依性,交換這兩道順序不會影響S2的執行.
2.Loop第一次執行,S1相依於此迴圈開始執行前的B[1]值.
化解為：
　A[1] = A[1] + B[1]
　for (i=1; i<=100; i=i+1) {
　　A[i] = A[i] + B[i];　　　/* S1 */
　　B[i+1] = C[i] + D[i];　　/* S2 */
　}
　B[101] = C[100] + D[100]
※ A recurrence is when a variable is defined based on the value of that variable in an earlier iteration, often the one immediately preceding, as in the above fragment.
Detecting a recurrence can be important for two reasons:
Some architectures (especially vector computers) have special support for executing recurrences, and some recurrences can be the source of a reasonable amount of parallelism.
※ Dependence distance :
　for (i=6;i<=100;i=i+1) {
　　Y[i] = Y[i-5] + Y[i];
　}
第I次執行時,Loop會讀取陣列元素i-5, Dependence distance = 5.
Dependence distance越大,the more potential parallelism can be obtained by unrolling loop.
※ Finding the dependences is important in 3 tasks :
1. Good scheduling of code.
2. Determining which loops might contain parallelism.
3. Eliminating name dependences.
※ Compiler 偵測 dependences ?
Nearly all dependence analysis algorithms work on the assumption that array indices are affine (仿射) : a one-dimensional array index is affine if it can be written in the form a × i + b, where a and b are constants, and i is the loop index variable. 而x[y[i]]就Nonaffine.
※ A dependence exists if two conditions hold: (GCD偵測)
1. There are two iteration indices, j and k, both within the limits of the for loop.
That is m ? j ? n, m ? k ? n.
2. The loop stores into an array element indexed by a × j + b and later fetches from that same array element when it is indexed by c × k + d. That is, a × j + b = c × k + d.
範例： Use the GCD test to determine whether dependences exist in the following loop:
　　for (i=1; i<=100; i=i+1) {
　　　X[2*i+3] = X[2*i] * 5.0;
　　}
解法： Given the values a = 2, b = 3, c = 2, and d = 0,
　　then GCD(a,c) = 2, andd – b = –3.
　　Since 2 does not divide –3, no dependence is possible.
=> GCD測試可保證沒相依性存在,但可能GCD測成功,但並沒相依性存在.
　(因為loop bounds沒考慮到)
※ Situation in which array-oriented dependence analysis (陣列導向的相依性分析) cannot tell us :
1. When objects are referenced via pointers.
2. When array indexing is indirect through another array.
3. When a dependence may exist for some value of inputs, but does not exist in actuality when the code is run since the input never take in those value.
4. When an optimization depends on knowing more than just the possibility of a dependence, but needs to know on which write of a variable does a read of that variable depend.
※ The basic approach used in points-to analysis (指向分析) replies on information from :
1. Type information(型別資訊), which restricts what a pointer can point to.
2. Information derived when an object is allocated or when the address of an object is taken, which can be used to restrict what a pointer can point to. (例: p指向X, q永不指向X, 則p和q就不能指向同一物件)
3. Information derived from pointer assignment. (p -> q -> X, q的值指定給p,則p指向q所指的物件)
※ Eliminating Dependent Computations (消除相依計算) :
1. Copy propagation (複製傳遞) : 用來避免複製運算 Eliminates operations that copy values.
　DADDUI　R1, R2, #4
　DADDUI　R1, R2, #4
　變成=> DADDUI R1, R2, #8
2. Tree height reduction (樹的高度縮減) :

　　　ADD R1,R2,R3
　　　ADD R4,R1,R6
　　　ADD R8,R4,R7
　　　　轉換 3 cycles => 2 cycles
　　　ADD R1,R2,R3
　　　ADD R4,R6,R7
　　　ADD R8,R1,R4
3.Recurrences (遞迴):
　　sum = sum + x;
　　sum = sum + x1 + x2 + x3 + x4 + x5 ;　　5 cycles
　　=> sum = ( (sum + x1) + (x2 + x3) ) + (x4 + x5) ;　　3 cycles
※ Software Pipeline(軟體管線) : Symbolic Loop Unrolling (象徵性迴圈展開) :
Software Pipeline(軟體管線) : Reorganize loops such that each iteration in the software-pipelined code is made from instructions chosen from different iterations of the original loop (從不同回合中挑選組合而成).
請參考 Fig4.6

※ Global Code Scheduling (全域程式碼排程):
1. Effective scheduling of a loop body with internal control flow will require moving inst. across branches.
2. Aims to compact a code fragment with internal control structure into the shortest possible sequence (Critical Path) that preserves the data and control dependence. (保留 data 與 control 相依性)
3. It can reduce the effect of control dependences arising from conditional nonloop branches by moving code.
4. Effectively using global code motion require estimates of the relative frequency of different paths.
※ Trace Scheduling (追蹤排程) : focusing on the Critical Path
1. Useful for processors with a large number of issues per clock.
2. A way to organize the global code motion process, so as to simplify the code scheduling by incurring the costs of possible code motion on the less frequent paths. (用於執行頻率有明顯差距的不同路徑上)
※ Two steps of Trace Scheduling :
1. Trace selection (追蹤選擇) : tries to find a likely sequence of basic blocks whose operations will be put together into a smaller number of instructions.
2. Trace compaction (追蹤壓縮) : Tries to squeeze the trace into a small number of wide instructions. (其實就是 code scheduling.)
The advantage of the Trace Scheduling approach is that it simplifies the decisions concerning global code motion. (Trace scheduling 優點在於簡化了 Global Code 移動的決策)
※ Superblocks (超級區塊) : 解決 Trace Scheduling 追蹤中間進入或離開造成十分複雜的情況
1. are formed by a process similar to that used for traces.
2. but are a form of extended basic blocks, which are restricted to a single entry point but allow multiple exists.
How can a superblock with only one entrance be constructed? The answer is to use tail duplication (尾部複製) to create a separate block that corresponds to the portion of the trace after the entry.
與一般的 Trace 產生方法比起來, 使用 superblocks能減少額外記錄(bookkeeping)與排程的複雜度, 但是程式碼可能會大於以 Trace 為基礎的方法. 所以, 如同Trace scheduling, Superblocks在其他技巧都行不通時再使用比較合適.

2007年12月17日 星期一
=== Ch4.2 Static Branch Prediction ===
※ Delayed branch can reduce the Control hazard.
程式範例：
　　　LD 　　 R1,0(R2)
　　　DSUBU R1,R1,R3
　　　BEQZ 　 R1,L
　　　OR 　　 R4,R5,R6
　　　DADDU 　R10,R4,R3
L: 　 DADDU 　R7,R8,R9
=> DSUBU and BENQZ depend on LD
=> stall will be needed after LD.
1. branch almost taken
　=> R7 was not needed on the fall-through path
　=> Could increase the speed by moving DADDU to the position after LD.
2. branch rarely taken :
　=> R4 was not needed on the taken path
　=> Could increase the speed by moving OR to the position after LD.
3. profiled-based strategy predictor : 用預先收集的早期執行概況來預測分支
=== Ch4.3 Static Multiple Issue : VLIW ===
※靜態 Statically scheduled superscalar requires compiler assistance.
※動態 Dynamically-scheduled superscalar requires less compiler assistance, but has hardware costs.
※VLIW : Very Long Instruction Word
在一道指令中納入很多運算(64~128 bits or more)
VLIWs use multiple, independent functional units. Rather than attempting to issue multiple, independent instructions to the units, a VLIW packages the multiple operations into one very long instruction, or requires that the instructions in the issue packet satisfy the same constraints.
※ Basic VLIW approach ---
1. Local scheduling tech :
　a.) the loop unrolling generates straight-line code.
　b.) Operate on a single basic block.
2. Global scheduling tech : (trace scheduling是特別為VLIW發展的全域排程技巧)
　a.) scheduling code across branches.
　b.) More complex in structure.
　c.) Must deal with significantly more complicated trade-offs in optimization.
※ For the original VLIW model, there are both technical and logistical problems.
=> The technical problems are the increase in code size and the limitations of lock-step operation.
※ Two different elements combine to increase code size substantially for a VLIW.
1, generating enough operations in a straight-line code fragment requires ambitiously unrolling loops (as earlier examples) thereby increasing code size.
2, whenever instructions are not full, the unused functional units translate to wasted bits in the instruction encoding.
=> 解increase code size方法 =>
1. Clever encodings (例如：讓數個function unit共用一個 large immediate field)
2. Compress the instructions in main memory
※ Early VLIWs operated in lock-step – T
here was no hazard detection H/W at all.
因為所有的 function unit 必須保持同步，所以任何一個管線發生stall，就會造成整個processor stall.
※ logistical : Binary code compatibility problem (執行碼相容性問題)
1. In a strict VLIW approach, the code sequence makes use of both the instruction set definition and the detailed pipeline structure.
2. Different numbers of functional units and unit latencies require different versions of code.
3. One possible solution is object-code translation or emulation.
4. Another approach is to temper the strictness of the approach, so that binary compatibility is still feasible.
※ Multiple Issue Processor兩個潛在的優點是Vector Processor所沒有的 :
1. has the potential to extract some amount of parallelism from less regularly structured code.
2. to use a more conventional, and typically less expensive, cache-based mem system.