标题: 星状网路上之程式最佳动态分配
An optimal dynamic partitioning in the star network
作者: 許文政
Xu, Wen-Zheng
曾憲雄
Zeng, Xian-Xiong
資訊科學與工程研究所
关键字: 星状网路;动态分配;静态分配;循序程式;多重电脑系统;资讯;电脑;电脑科学;IBMRS-6000/320工;BOKHARI;1988;INFORMATION;COMPUTER;INFORAMTION;COMPUTER-SCIENCE
公开日期: 1990
摘要: 所谓的分配问题,乃是给定一个用某种特殊连接结构相连的多重电脑系统,以及一些
彼此以某种方式联系之模组所构成的程式。我们的目的便是希望将这些程式用某种方
式分配给这些处理机去执行,使得执行它们所需的总代价为最低。
Bokhari 在1988提出一演算法用以解决如何将多个任意架构的循序程式置于星状网路
上执行的静态分配问题,而使得其执行和联系的时间为最短。在这篇论文中,我们将
考虑多个任意架构的循序程式如何放在星状网路上执行的动态分配问题。我们将Bolh
an的静态分配模式加以延伸并提出一动态分配演算法来求得一最佳动态分配使得系统
所需之执行、联系和搬移的总时间为最短。其中静态和动态分配的最大区别在于:若
是采用静态分配,则任一模组在整个程式的执行过程中始终固定在某一处理机上执行
。但若是采用动态分配,则任一模组可在程式执行过程中,任意地在不同的处理机间
作搬动,而使得程式的执行更具效率。
当搬移时间趋近无穷大时,我们证明动态演算法的解和静态的解相等。为了评估该演
算法262 个例子被模拟在IBMRS6000/320 工作站上,我们演算法所需的时间除以Bodh
ari的时间的平均比率值约为0.865。从这些实验可归纳出我们的演算法不错。最后,
文中并有结论和今后继续研究的方向。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT794394001
http://hdl.handle.net/11536/55592
显示于类别:Thesis