超並列回路解析法の研究

大规模并联电路分析方法研究

基本信息

批准号：
07780229
负责人：
須田礼仁
金额：
$ 0.64万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780229/
关键词：
回路シミュレーション反復解法並列処理 LU分解の修正

项目摘要

本研究ではまず前処理つき緩和法の高い並列性を効率良く実装する技術について研究を行ない発表を行なった。そこでは第一に、前処理行列U^<-1>L^<-1>のプロセッサへのマッピング手法を比較検討し、L^<-1>を列毎に、U^<-1>を行毎にマッピングする方法が,ロードバランスと通信量の両面で優れていることを示した。第二に前処理にかかる通信手法について研究を行ない、上記のマッピングのもとではバタフライ型の通信方式が一対一の通信よりも優れていることを示した。次に、前処理つき緩和法を拡張して半導体回路にも使うことのできる解法である強制疎化LU分解法を提案し、研究を行なった。この方法はLU分解を部分的に再計算することによって前処理行列の更新を行なう前処理つき緩和法である。強制疎化LU分解法は部分的に行列分解の修正を行なうILU緩和法の拡張とみなすことができるが、ILU緩和法に比べ、回路のレイテンシを有効に活用して計算量を効率的に低下させることができる特長がある。この強制疎化LU分解法について、まず強制疎化の閾値と反復回数及び所要時間の関係を研究し、シミュレーション精度のおよそ半分が閾値として最適であることを実験的に示した。この場合99%の確率で1反復で収束するので、計算時間が1%程度増加する代わりに反復に関わるコストを削減することのできる「簡略化強制疎化LU分解法」を提案した。さらにこれらの方法が直接法よりも高速であり、その差は大規模回路ほど大きくなることを実験によって示した。

在本研究中，我们首先进行了研究并提出了一种有效实现预处理松弛方法的高并行性的技术。首先，我们比较和研究了预处理矩阵 U^<-1>L^<-1> 到处理器的映射方法，结果表明逐行映射方法在负载均衡和流量方面均具有优越性。。其次，我们研究了与预处理相关的通信方法，并表明在上述映射下蝴蝶通信方法优于一对一通信。接下来，我们提出并研究了强制稀疏LU分解方法，该方法是预处理松弛方法的扩展，可用于半导体电路。该方法是一种带预处理的松弛方法，通过部分重新计算 LU 分解来更新预处理矩阵。强制稀疏LU分解方法可以看作是对矩阵分解进行部分修改的ILU松弛方法的扩展，但与ILU松弛方法相比，它具有有效利用电路延迟、高效减少计算量的特点。习惯于对于这种强制稀疏化LU分解方法，我们首先研究了强制稀疏化阈值、迭代次数和所需时间之间的关系，并通过实验表明大约一半的模拟精度是最佳阈值。在这种情况下，一次迭代有 99% 的概率收敛，因此我们提出了一种“简化的强制稀疏 LU 分解方法”，该方法可以以增加约 1% 的计算时间为代价来减少与迭代相关的成本。此外，我们通过实验表明这些方法比直接方法更快，并且随着电路变大，差异也变得更大。