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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:侯一安
研究生(外文):Hou Yi-An
論文名稱:應用張量乘積將混合基底多階層連結網路模式化
論文名稱(外文):Modeling Mixed-Radix Multistage Interconnection Networks Using Tensor Products
指導教授:黃秋煌黃秋煌引用關係
指導教授(外文):Chua-Huang Huang
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:68
中文關鍵詞:張量乘積多階層連結網路混合基底路由
外文關鍵詞:tensor productmultistage interconnection networksmixed-radix routing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:71
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在這篇論文中,我們介紹張量乘積的架構並使用張量乘積的表示法將一個新的多階層連結網路模型─混合基底多階層連結網路 (Mixed-Radix Multistage Interconnection Networks)模式化。混合基底多階層連結網路是由二元多階層連結網路延伸而來的,而且與傳統的多階層連結網路相較之下,混合基底多階層連結網路更為有彈性及更有實用價值。我們不僅介紹混合基底多階層連結網路在張量基底表示法的通式,同時還將許多實際存在的連結網路對映至混合基底多階層連結網路的模型之下。
張量乘積表示法已經證明在產生平行指令與向量指令方面以及對於一些較複雜的索引計算中自動產生程式碼是有用而且可靠的。同時,張量乘積表示法對於電腦演算法及架構的便利表示也顯示它的多用性。
為了解決在混合基底多階層連結網路上路由的問題,我們提出的一個針對混合基底多階層連結網路上一對一路由的混合基底路由 (Mixed-Radix Routing) 演算法。同時,我們也可以透過修改混合基底路由演算法來達到混合基底多階層連結網路上一對多的路由要求。另一方面,混合基底多階層連結網路模型也是很有實用價值的,我們將k-way bitonic sort 實際應用於混合基底多階層連結網路之上,並且介紹一個在混合基底omega網路上的k-way bitonic sort實例。

In this thesis, we introduce the tensor product framework, and use tensor product formulation to model the new multistage interconnection network model─Mixed-Radix Multistage Interconnection Networks, which is extended from the binary multistage interconnection network and will be more flexible and practical than the traditional multistage interconnection networks. We not only show the generalized formulation of the mixed-radix multistage interconnection networks but also mapping several realistic interconnection networks on it.
The tensor product formulation has been proven to be useful for extracting parallel and vector operations and for automatically generating code for complex index computations, and its representation is more versatile to represent both algorithms and architectures.
To solving the routing problems in mixed-radix multistage interconnection networks, we propose the Mixed-Radix Routing algorithm for one-to-one routing and modify it to solve the one-to-many routing request. On the other side, the model of mixed-radix multistage interconnection networks can be very practical. We map the k-way bitonic sort on mixed-radix multistage interconnection networks and show an example based on the mixed-radix omega network.

TABLE OF CONTENTS
DEDICATION Ⅱ
ACKNOWLEDGEMENTS Ⅲ
ABSTRACT Ⅴ
LIST OF TABLES Ⅶ
LIST OF FIGURES Ⅷ
Chapter 1. Introduction 1
Chapter 2. The Tensor Product Notation 5
Chapter 3. Binary Multistage Interconnection Networks 10
3.1 Topology, Switching Element and Control Structure, and Network Representation 12
3.2 Representation of Binary Multistage Interconnection Networks 13
Chapter 4. Mixed-Radix Multistage Interconnection Networks 24
4.1 Overview of Mixed-Radix Multistage Interconnection Networks 24
4.2 Representation of Mixed-Radix Multistage Interconnection Networks 28
Chapter 5. Routing in Mixed-Radix Multistage Interconnection Networks 41
5.1 Mixed-Radix Routing Algorithm 42
5.2 One-to-Many Routing Algorithm 46
Chapter 6. Sorting in Mixed-Radix Multistage Interconnection Networks 50
6.1 K-Way Bitonic Sort 50
6.2 K-Way Bitonic Sort on Mixed-Radix Multistage Interconnection Networks 53
Chapter 7. Conclusions and Future Works 55
Bibliography 57
LIST OF TABLES
Table 1-1: Summary of Dynamic Interconnection Network Characteristics 2
LIST OF FIGURES
Figure 3-1: The schematic of a typical multistage interconnection network 10
Figure 3-2: Recursive process to the baseline network. 16
Figure 3-3: Baseline Network for N=2n=8. 17
Figure 3-4: Reverse Baseline Network for N=2n=8. 18
Figure 3-5: Indirect Binary n-cube Network for N=2n=8 20
Figure 3-6: Generalized Cube Network for N=2n=8 21
Figure 3-7: Omega Network for N=2n=8 22
Figure 3-8: Flip Network for N=2n=8 23
Figure 4-1: The schematic of the mixed-radix multistage interconnection networks 25
Figure 4-2: Mixed-Radix Baseline Network for
N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 30
Figure 4-3: Mixed-Radix Reverse Baseline Network for
N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 32
Figure 4-4: Mixed-Radix Indirect Binary n-cube Network for
N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 34
Figure 4-5: Mixed-Radix Generalized Cube Network for
N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 36
Figure 4-6: Mixed-Radix Omega Network for
N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 38
Figure 4-7: Mixed-Radix Flip Network for
N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 40
Figure 5-1: The Mixed-Radix-Routing algorithm 42
Figure 5-2: Routing S( : 020) to D( : 023) on Mixed-Radix Omega
Network for N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 44
Figure 5-3: Routing S( : 020) to D( : 023) on Mixed-Radix Flip
Network for N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 45
Figure 5-4: The One-to-Many Baseline Routing algorithm 47
Figure 5-5: Routing (101) to (101)(121)(301)(321) on Mixed-Radix Baseline
Network for N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 48
Figure 5-6: The One-to-Many Indirect Binary n-Cube Routing algorithm 49
Figure 6-1: The comparison-exchange module 50
Figure 6-2: 4-bitonic merger and 4-regular-bitonic merger. 51
Figure 6-3: A 4-sorter (bitonic) 52
Figure 6-4: The 30-bitonic-merger on mixed-radix omega network of size
N = n0 n1 n2 = 30, and n0=2, n1=3, n2=5 54

[BaHi94] Baron, R.J., Higbie, L., Computer Architecture. Addison-Wesley, 1994.
[Bat68] Batcher, K.E., "Sorting networks and their applications". Proceedings of AFIPS Spring Joint Computer Conference, Vol. 32, April 1968, pp. 307-314.
[Bat76] Batcher, K.E., "The Flip Network in STARAN". International Conference on Parallel Processing, 1976, pp.65-71.
[Bat80] Batcher, K.E., "Design of a Massively Parallel Processor". IEEE Transactions on Computers, Vol. 29, No. 9, 1980, pp. 836-844.
[Bat82] Batcher, K.E., "Bit Serial Parallel Processing Systems". IEEE Transactions on Computers, Vol. 31, No. 5, 1982, pp. 377-384.
[Ble90] Blelloch, G.E., Vector Models for Data-Parallel Computing. The MIT Press, 1990.
[Cole88] Cole, R., "Parallel merge sort" SIAM J. Comput., 17(4), August 1988.
[CoTr95] Cosnard, M., Trustram, D., Parallel Algorithms and Architectures. International Thomson Computer Press, 1995.
[Feng74] Feng, T., "Data Manipulating Functions in Parallel Processors and Their Implementations". IEEE Transactions on Computers, Vol. 23, No. 3, 1974, pp. 309-318.
[Fly95] Flynn, M.J., Computer Architecture─Pipelined and Parallel Processor Design. Jones and Bartlett, 1995.
[Gra81] Graham, A., Kronecker Products and Matrix Calculus: With Applications, Ellis Horwood Limited, 1981.
[Hay88] Hayes, J.P., Computer Architecture and Organization. McGRAW-HILL, 1988.
[HoJo81] Horn, R.A. and Johnson, J.R., Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1981.
[HJJ90] Huang, C.-H., Johnson, J.R., and Johnson, R.W., "A Tensor Product Formulation of Strassen's Matrix Multiplication Algorithm". Appl . Math Letters, Vol. 3, No. 3, 1990, pp. 67-71.
[HJJ92] Huang, C.-H., Johnson, J.R., and Johnson, R.W., "Generating Parallel Programs from Tensor Product Formulas: A Case Study of Strassen's Matrix Multiplication Algorithm". International Conference on Parallel Processing, 1992, pp. 104-108.
[Hwa93] Hwang, K., Advanced Computer Architecture─Parallelism Scalability Programmability. McGRAW-HILL, 1993.
[JHJ91] Johnson, R.W., Huang, C.-H., and Johnson, J.R., "Multilinear Algebra and Parallel Programming". Journal of Supercomputing, Vol. 5, 1991, pp. 189-218.
[KGGK94] Kumar, V., Grama, A., Gupta, A., Karypis, G., Introduction to Parallel Computing─Design and Analysis of Algorithms. The Benjamin/Cummings, Redwood, Ca, 1994.
[KSH93] S.D. Kaushik, S. Sharma, and C.-H. Huang, "An algebraic Theory for Modeling Multistage Interconnection Networks". Journal of Information Science and Engineering, Vol. 9, 1993, pp. 1-26.
[Lang76] Lang, T., "Interconnections between Processors and Memory Modules Using Shuffle-Exchange Networks". IEEE Transactions on Computers, Vol. 25, No. 5, 1976, pp. 496-503.
[Law75] Lawrie, D.K., "Access and Alignment of Data in an Array Processor". IEEE Transactions on Computers, Vol. 24, No. 12, 1975, pp. 1145-1155.
[Lei92] Leighton, F.T., Introduction to Parallel Algorithms and Architectures: arrays, trees, hypercubes. Morgan Kaufmann, San Mateo, Ca, 1992.
[NHAT89] Nakatani, T., Huang, S.T., Arden, B.W., Tripathi, S.K., "K-Way Bitonic Sort". IEEE Transactions on Computers, Vol. 38, No. 2, 1989, pp. 283-288.
[Pea77] Pease III, M.C., "The Indirect Binary n-cube Microprocessor Array". IEEE Transactions on Computers, Vol. 26, No. 5, 1977, pp. 458-473.
[Qui94] Quinn, M.J., Parallel Computing─theory and practice. McGRAW-HILL, 1994.
[Reif93] Reif, J.H., Synthesis of Parallel Algorithms. Morgan Kaufman, San Mateo, Ca, 1993.
[Sie79] Siegel, H.J., "Interconnection Networks for SIMD Machines". IEEE Computer, 1979, pp. 57-65.
[Sie89] Siegel, H.J., "Using the Multistage Cube Network Topology in Parallel Computers". Proceedings of IEEE, Vol.77, No. 12, 1989, pp. 1932-1953.
[Sie92] Siegel, H.J., Interconnection Networks for Large-Scale Parallel Processing─theory and case studies. McGRAW-HILL, 1992.
[Sto71] Stone, H.S., "Parallel Processing with the Perfect Shuffle". IEEE Transactions on Computers, Vol. 20, No. 2, 1971, pp. 153-161.
[WuFe80]Wu, C.-L. and Feng, T., "On a Class of Multistage Interconnection
Networks". IEEE Transactions on Computers, Vol. 29, No. 8, 1980, pp. 694-702.

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