(3.215.180.226) 您好!臺灣時間:2021/03/09 01:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:莊德源
研究生(外文):Deh-Yuan Chuang
論文名稱:應用分享類別於分散式共用記憶體系統上引線配置之研究
論文名稱(外文):Applying Sharing Types on Thread Mapping for Software Distributed Shared Memory Systems
指導教授:謝錫
指導教授(外文):Ce-Kuen Shieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:42
中文關鍵詞:通訊量減少分散式共用記憶體共享程度分享類別存取類別引線配置引線遷移
外文關鍵詞:Communication MinimizationDSMSharing DegreeSharing TypesAccess TypesThread MappingThread Migration
相關次數:
  • 被引用被引用:0
  • 點閱點閱:62
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在分散式共用記憶體上,減少維持資料一致性所產生的通訊量是一項重要的考量。應用資料共享來從事引線搬移是被提出的解決方案之一。之前的研究使用記憶體頁共享程度,來預測引線之間因共享記憶體頁而將產生的通訊量,並利用預測的結果,將彼此通訊量較重的引線對優先配置在同一個節點上,以達通訊量減少的目的。然而,資料共享可進一步被區別成三種分享類別,即讀/讀、讀/寫、寫/寫,在鬆散一致性模組下,相對應於這三種分享類別所需的通訊量是不同的,不考慮分享類別可能會造成不適當的引線配置。
在本論文,我們提出一個新的策略,即應用分享類別於分散式共用記憶體上的引線配置。這個概念的主要精神在於區別出分享類別,並在預測通訊量時給予不同的加權,使引線配置演算法可以集中注意於消除寫/寫和讀/寫的共享記憶體頁。我們在Cohesion系統上將這一個策略應用於引線配置。評估的結果顯示出分享類別必須被區別,以便能更有效的消除通訊量。

Minimizing the communication created for maintaining data consistency is an important issue for the performance of software distributed shared memory (DSM) systems. One solution of addressing this issue is exploiting data sharing in thread migration. In order to reduce communication, the previous work usually uses share degree, i.e., the number of shared pages to predict the amount of communication caused by the sharing among threads. Then, they locate the pair of threads that will cause the most communication under prediction on the same node in priority. However, the sharing between a pair of threads to a page can be further divided into read/read, read/write, and write/write sharing. The amount of communication induced by this thread pair's sharing to this page will vary from type to type if they are located on different nodes, based on release consistency protocol. It is possible to make a wrong decision in thread mapping if sharing types is ignored. In this paper, we propose a novel policy to exploit data sharing in thread mapping for DSM systems. The basic concept of this policy is to distinguish the types of sharing among threads to pages, and then put effort only on the reduction in write/write and read/write sharing. We have applied this policy to thread mapping in a DSM system called Cohesion. The evaluation shows that sharing types distinguishing is important and necessary to minimize communication in DSM systems. The communication cost of an application can be more effectively reduced by thread mapping with considering sharing types than that of only considering sharing degree when the threads of the application share the same pages in different types.

Contents
CONTENTSI
ILLUSTRATIONSII
TABLESIII
CHPATER 1 INTRODUCTION1
CHAPTER 2 EXPERIMENTAL ENVIRONMENT4
2.1 COHESION4
2.2 COHESION KERNEL6
2.3 OBJECT MANAGER AND THREAD SYSTEM8
2.4 APPLICATIONS10
CHAPTER 3 APPLYING SHARING TYPES12
3.1 SHARING TYPES13
3.2 TYPED INFORMATION15
3.3 THREAD MAPPING16
3.3.1 Thread Correlation Map17
3.3.2 The Thread Migration and Exchange Algorithm19
3.3.3 The Descend Edge Algorithm20
CHAPTER 4 PERFORMANCE EVALUATION23
4.1 APPLICATIONS23
4.1.1 Successive-Over-Relaxation23
4.1.2 N-body25
4.1.3 Vector Quantization26
4.1.4 Gaussian Elimination28
4.2 RESULT ANALYSIS AND TOOLS29
4.2.1 Experimental Results29
4.2.2 Variation of Sharing Degree32
4.2.3 Ordering Deviation34
CHAPTER 5 RELATED WORK37
CHAPTER 6 CONCLUSION38
BIBLIOGRAPHY40

[Anderson 92]T. E. Anderson, B. N. Bershad, E. D. Lazowska, and H. M. Levy: "Scheduler Activations: Effective kernel support for the user=level management of parallelism," in ACM Transactions on Computer Systems, 10(1) pp. 53-79, Fevuary, 1992
[Angus 90]I. Angus, G. Fox, J. Kim, D. Walker: Solving Problems on Concurrent Processors vol 2, Perntice Hall, New Jersey, USA, 1990
[Bershad 88]Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy: "PRESTO: A System for Object-Oriented Parallel Programming," Software-Practice and Experience, 18980, August, 1988
[Bershad 93]Brian N. Bershad, Zekauskas, M.J.: "The Midway Distributed Shared Memory System," in Proceedings of IEEE COMPCON Conference, IEEE, pp. 528-537, 1993
[Casavent 88]Thomas L. Casavant and John G. Kuhl: "A taxonomy of Shceduling in General-Purpose Distributed Computing Systems," IEEE Trasactions on Software Engineering, vol. SE-8, no.4, July, 1988
[Farkas 92]K. Farkas, Z.Vranesic, and M. Stumm: "Cache Consistency in hierarchical-Ring-Based Multiprocessors," in Proceedings of Super 92, pp. 348-357, Nov. 1992
[Freeh 94]Vincent W. Freeh, David K.Lowenthal, and Gregory R. Andrews.: "Distributed Filaments: Efficient Fain Grain Parallelism on a Cluster of Workstations," in Proceedings of First Symposium on Operating Systems Design and Implement, pp. 201-212, Monterey, CA, November, 1994
[Gharachorloo 90]Gharachorloo, K., Lenoski, D., Laudon, J., Gibbons, P., Gupta, A., and Hennessy, J.: "Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors," in Proceedings of 17th Ann. International Symposium on Computer Architecture, ACM, pp. 15-26, 1990
[Iftode 96]Livir Iftode, Jaswinder Pal Singh, and Kai Li: "Scope Consistency: A Bridge between Release Consistency and Entry Consistency," in Proceedings of 8th Annual ACM Symposium on Parallel Algorithms and Architectures, June, 1996
[Itzkovitz 96]A. Itzkovitz, A. Schuster, and L. Wolfovich, "Thread Mirateion and its Applications in Distributed Shared Memory Systems," Technion IIT LPCR #9603, July 1996
[Keleher 96]Pete Keleher: "The Relative Importance of Concurrent Writers and Weak Consistency Models," in Proceedings of the 16th International Conference on Distributed Computing Systems, 1996
[Li 86]Kai Li: "Shared Virtual Memory on Loosely Coupled Multi-processors," Ph.D. Thesis, Yale Univ., 1986
[Li 88]Kai Li: "IVY: A Shared Virtual Memory System for Parallel Computing," In Proceedings of 1988 IEEE International Conference on Parallel Processing, pp. 94-101, August, 1988
[Liu 97]Deh-Chang Liu, Ce-Kuen Shieh, and Tyng-Yue Liang: "Dynamically Scheduling Threads on Cohesion," Master Thesis, National Cheng Kung University, July, 1997
[Marsh 91]B. D. Marsh, M. L. Scott, T. J. LeBlanc, and E. P. Markatos: "irst-Class User-Level Threads," in Proceedings of the 13th ACM Symposium on Operating Systems Principles, October 1991
[Raynal 93]M. Raynal and M. Mizuno: "How to find his way in the jungle of consistency criteria for distributed shared memories" in Proceedings of FTDCS 93, pp. 340-346, 1993
[Shieh 95]Ce-Kuen Shieh, An-Chow Lai, Jyh-Chang Ueng, Tyng-Yue Liang, Tzu-Chiang Chang, and Su-Cheong Mac: "Cohesion: An Efficient Distributed Shared Memory System Supporting Multiple Memory Consistency Models," in Proceedings of the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis, Aizu-Waka-matsu, Fukushima, Japan, March, 1995
[Sudo 97]Y. Sudo, S. Suzuki, and S. Shibayama, "Distributed-Thread Scheduling Methods for Reducing Page-Thrashing," in Proceedings of the 6th IEEE International Symposium on High Performance Distributed Computing, 1997
[Thitikamol 99]Krichalach Thitikamol and Pete Keleher: "Active Correlation Tracking," in Proceedings of the 19th ICDCS, May 1999
[Thitikamol 99a]Krichalach Thitikamol and Pete Keleher: "Thread Migration and Communication Minimization in DSM systems," in Proceedings of IEEE, vol 87, no.3, pp. 487-497, Mar. 1999

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔