以硬體作法執行具有相依性關係的迴圈

Abstract

一般程式最主要的平行化來源，就是DO迴圈。當我們將一個已經平行化的 迴圈之每個重述放入一個具有共享記憶體的多處理機系統上執行時，必須 對重述之間的資料相依性關係強制加入同步指令，俾使其能正確執行。現 存的同步指令方法不是太過限制而不實際，就是由於大量的執行時期負擔 而缺乏效率。在本篇論文中，我們提出一個硬體的機制消除同步指令的必 要性，前人的方法都是需要在迴圈中嵌入同步指令以確保相依性關係的。 此外，由於巧妙的硬體架構設計，臨界區間是沒有必要使用的。我們的分 析進一步指出，本架構所承受的執行時期負擔不大，可以接受。因此我們 可以得知，使用本篇論文的方法在多處理機上執行迴圈的效果，比前人的 方法還要好。 The major source of parallelism in ordinary programs is do loops. When loop iterations of parallelized loops are executed on a shared memory multiprocessors system, the cross-iteration data dependences need to be enforced by synchronization instructions to ensure the correct execution. Existing data synchronization schemes are either too restrictive to be practical, or too inefficient due to large run-time overhead. In this thesis, we propose a hardware mechanism to eliminate the necessity of synchronization instructions which is required by former schemes to be embedded into loops, ensuring the data dependences. Also, the usage of critical section is not needed at all due to skillful design of our hardware architecture. Furthermore, according to the analysis, the run-time overheads of our architecture is small to be acceptable. So we may conclude that to execute loops over multiple processors, our method is believed to be good compared with former researches.