在具有快取記憶體一致性的多處理機系統下, 以引線排程方式解決共享資料問題

Abstract

隨著電腦的快速發展，平行處理已成為目前的趨勢. 利用平行處理的方 式, 我們可以加快程式的執行速度, 因此平行處理的重要性與日俱增.為 了配合平行處理的需要, 具有快閃記憶體一致性的多處理機系統應運而 生. 雖然這類系統擁有許多優點, 然而此系統會產生資料共享的問題( sharing problem).資料共享問題包括了真正共享的資料(true sharingdata)與非真正共享的資料(false sharing data)所造成的問題. 這些問題經常造成存取快取記憶體時的失誤現象(cache miss)並增加匯流 排(bus)的負擔而導致系統的整體效能降因此, 在這篇論文中, 我們將提 出方法來解決這個問題.目前所提出解決的方法, 是純然用編譯器來對資 料做重新安置, 以去除非真正共享的資料. 然而這些方法有其缺點存在. 且在傳統的引線排程中, 並未探討這類的問題. 所以我們提出新的引線排 程方法對此問題做一處理. 我們將有資料共享的引線, 分開在不同的時段 來執行, 如此雖仍有共享資料或非共享資料的存在, 但卻不會造成共享資 料的問題. 此外, 我們也建立了一個模擬具有快閃記憶體一致性的多處理 機系統環境, 來比較分析我們的方法與傳統排程方法之間的差異數據結果 顯示, 我們所提出的方法, 可以解決大部份資料共享的問題, 並能提升系 統的整體效能. With the rapid development of computers, parallel computing has become atrend in solving complex problems. Since we can speed up the execution ofprograms by parallel computing in multiprocessors, parallel computing isincreasingly important.In addition, the cache coherent multiprocessor systemis frequently used for parallel computing. Though there are many advantagesof using cache coherent multiprocessors, the sharing problems, including thetrue sharing and the false sharing, will occur in this system. These problemswill increase a large number of cache misses and increase the bus contention.Therefore, we proposed an approach to solve the sharing problem.The compilertechniques for reducing the false sharing data were proposed before. It avoidsthe sharing problem by reallocating the false sharing data. However, thereare some disadvantages of using these techniques. Moreover, the sharingproblem is not considered in the conventional thread scheduling schemes.Thus we propose new thread scheduling schemes for reducing the overheadespecially caused by the false sharing problem. We dispatch the threads, which will incur the sharing problem, into different tim e slices. By usingthis approach, we can avoid the sharing problem. We also construct a simulatedcache coherent multiprocessor system environment, and execute parallel programto testify our scheduling schemes. We compare the performance of using aconventional scheduling scheme with that of using our scheduling schemes.The result shows that our scheduling scheme can largely reduce the overheadcaused by the sharing problem. Therefore, we can use our scheduling schemesto improve the system performance.