設計能時效產生基本組成個體之平行演算法

Abstract

在離散計算(Combinatorial Computing)的領域�,我們 經常需要產生一些基本的組成個體(Combinatorial Object),常遇到的組成個體有排列(Permutation),組合( Combination),整數分割(Partitions ofInterger)......等等. 在文獻方面,已有許多論文提出演算法(Algorithm)以 產生這些基本的組成個體.早期的論文中大都提供順序演算法(Sequential Algorithm)來解決此問題,然 而,近來由於平行計算(Parallel Computing)的研究蓬勃 發展,已有許多的平行演算法被陸續的提出,在這 些平行演算法中,有些並不是很有效率(Efficient), 有些卻需要在複雜的計算模式(ComputationModel)上 運作,針對此,本計畫擬研究如何設計有效率的平 行演算法來產生一些重要的組成個體,並且將這 些演算法映射(Map)到簡單的規律陣列(Regular Array) 上.由於規律陣列具有同步執行(Sychronous),鄰近相 連(Local-connected)及模組化(Modular)之特性,所以,規 律陣列非常適合採用超大型積體電路(VLSI)的技術 製造之.簡言之,我們想設計規律陣列及平行演算 法以有效的產生基本組成個體,我們將主要的研 究內容條列如下:1,研讀(Survey)並分析已有的順序(Sequential)和平行( Parallel)演算法(產生基本組成個體者).2,設計有效率的平行演算法以產生如排列( Permutation),分割(Partition),及切割(Composition)等基本 組成個體.