跳到主要內容

臺灣博碩士論文加值系統

(100.28.227.63) 您好!臺灣時間:2024/06/16 20:26
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:呂景隆
研究生(外文):Jing-Long Benjamin Lu
論文名稱:多處理器系統中利用加權串之程式分割法
論文名稱(外文):Program Partitioning with Bundling Approach in a Multiprocessor System
指導教授:李良德李良德引用關係
指導教授(外文):Liang-Teh Lee
學位類別:碩士
校院名稱:大同工學院
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:50
中文關鍵詞:程式分割資料流程圖相對應權重串掛
外文關鍵詞:Program partitioningDFGRelative weightBundles
相關次數:
  • 被引用被引用:0
  • 點閱點閱:90
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
一般而言,平行處理的成效倚重於程式中的主要因素如:通訊成本和延遲時間。但大部分的程式分割方法都僅針對於特定研究範圍。本文提出了一個可自動產生程式分割的系統化程序,它包含了確認運算間相依關係的有效方法而又免去了傳統圖形分割的複雜性。整體的演算過程是相當的淺顯易懂,分割的結果以鏈結型態呈現,使得它只需極少數的轉換介面便可以為其它架構所應用。也就是說,我們的分割結果與架構沒有一定的相依性。在我們的演算過程中採用了資料流程圖的概念,再配合適當的工具如:SISAL和IF1,讓我們可以避免一般圖形分割的複雜程序。為了協助程式分割的執行,我們賦予不同的運算相對應的權重,而分割後的運算群則被分為不同的串掛以有效提昇使用時的便利性,並且可根據處理器的數目進行必須的串掛融合或分割。本文所提出之方法經模擬後亦可得到可接受範圍內之加速比,證明其為一有效的程式分割程序。

It is well understood that the extent to which parallel computing is successful depends largely on the performance of the underlying parallel programming primitives. There are many partitioning algorithms have been discussed, and majorities of them are focusing on the partitioning algorithm of specific area. We are here to present a systematic process of program partitioning and the process is done automatically after the program is coded. It includes an efficient method to identify the dependency relation between operations without the conventional complication of graph partition. The idea of entire approach is simple and straightforward. The result of our partition is prepared as link list and can be used by other architectures with only a few extra transformation interfaces. Our approach involves using Dataflow Graph (DFG) and proper tools to avoid the complication of graph partition. Relative weights are applied to the corresponding nodes in the DFG to aid the partitioning process. The partitioned groups of nodes are separated into different “Bundles” and can be used for easy reference. According to the processor number, the bundles can either be merged or partitioned again to achieve better processor utilization. By carefully managing these bundles, a feasible speedup are obtained through our simulated model.

LIST OF FIGURES IX
1. INTRODUCTION 1
2. BACKGROUND 4
2.1 THE ATTEMPT 4
2.2 DATAFLOW GRAPH 7
2.3 SISAL 8
2.4 IF1 10
3. GRAPH MAPPING AND PARTITIONING 13
3.1 GRAPH MAPPING 14
3.2 PROGRAM PARTITIONING WITH BUNDLING APPROACH 20
4. SIMULATION MODEL AND EFFICIENCY MEASUREMENT 29
4.1 THE SIMULATION MODEL 29
4.2 EFFICIENCY MEASUREMENT 31
5. CONCLUSION AND REMARK 36
REFERENCE 37
APPENDIX 38
A. THE MAPPING PROGRAM OF IF1 TO LINK LIST. 38
B. THE SIMULATED LIVERMORE LOOP 42
C. SIMULATED MATRICES MULTIPLICATION PROGRAM 44

[1] Bokhari, S., “Partitioning problem in parallel, pipelined, distrubuted computing,” IEEE transactions on computers, vol. 37, No. 1, pp. 48-57, January 1988.
[2] DeBoni, T. and Feo, J. and Rodrigue, G. and Muller, J., “Implementation and performance of a domain decomposition algorithm in sisal,” Hawaii international conference on system sciences, January 1994.
[3] Feo, John T. and Cann, David C.; Oldehoeft, R. R., “A report on the SISAL language project,” Journal of parallel and distributed computing, 1990.
[4] Gajski, D.D. and Peir, J., “Essential issues in multiprocessir system,” IEEE Computer Magazine., vol. 18, pp.9-27, June 1985.
[5] Jonsson, J., Vasell, J., “On Objective Function Selection in List Scheduling Algorithms for Digital Signal Processing Applications,” Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 667-670, Apr. 1997.
[6] Lee, L., Wei, C., “An efficient dataflow architecture for macro actor processing,” Proceeding of workshop on CPU research and development, pp. 59-63, May 1995.
[7] Padua, D. A., “Multiprocessors: Discussion of theoretical and practical problems,” Ph.D. dissertation, Rep.UIUCDCS-R-79-990, Univ. of Illinois at Urbana-Champaign, Urbana, IL, Nov. 1979.
[8] Peir, J. K. and Cytron, R., “Minimum distance: A method for partitioning recurrences for multiprocessors, “ International Conference of Parallel processing, pp. 217-225, 1987.
[9] Peir, J. K. and Gajski, D. D., “ Camp: A programing aid for multiprocessors,” International Conference of Parallel processing, pp. 475-482. 1986
[10] Peir, J. K., “Program partitioning and synchronization on multiprocessor systems,” Ph.D. dissertation, Rep.UIUCDCS-R-86-1259, Univ. of Illinois at Urbana-Champaign, Urbana, IL, Mar. 1986.
[11] Skedzielewski, S., “IF1: an intermediate form for applicative languages,” Lawrence Livermore national laboratory, ver. 1.0, July 1985.
[12] Stone, H., “A shortest tree algorithm for optimal assignments across space and time in a distributed processor system,” IEEE Transaction on Software Engineering, vol. SE-7, pp. 583-589, Nov. 1981.
[13] Stone, H., “Multiprocessor scheduling with the aid if network flow algorithms,” IEEE Transaction on Software Engineering, vol. SE-4, pp. 254-258, May 1978.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top