标题: | 一个有效不规则相依回圈计算与资料分解方法之研制 A Study on Effective Computation and Data Decomposition Techniques for Non-uniform Dependence Loops |
作者: | 李佳霖 Chia-Lin Lee 陈正 Cheng Chen 资讯科学与工程研究所 |
关键字: | 不规则相依回圈;计算分配;资料分配;non-uniform dependence loops;computation decomposition;data decomposition |
公开日期: | 1998 |
摘要: | 由于远端记忆体存取(Remote memory access)时间远大于区域记忆体存取(Local memory access)。因此,我们利用计算分解与资料分解之架构计算出回圈中计算(iteration)与阵列资料之相关性。并采用广域资料分析,对整个程序中之回圈进行阵列资料分析,促使阵列资料分解型态一致,以减少资料重组沟通。同时利用回圈交换方法,促使回圈中之计算对阵列资料之存取顺序能符合资料之区域性。最后,经由资料型态之分析决定出最后之区块或循环分配方式,将具有相关性之计算与资料分配到同一个处理器和其区域记忆体中。初步评估结果显示,当阵列之下标函数之变数较为复杂时,本方法能经由计算与资料分解之分配方式,降低远端资料存取顺序。而当回圈之计算顺序会破坏阵列资料之区域性时,本方法会利用回圈交换方式,使其存取顺序满足资料之区域性,进而降阺远端存取次数。因此,将此方法搭配不规则相依回圈静态排程方式,确可减少回圈中远端存取之次数。 In distributed shared memory multiprocessors, local memory access are much faster than remote access. For the sake of reducing remote communication, the array elements in programs must be precisely distributed to local memory for parallel execution. In this thesis, we have developed an efficient computation and data decomposition method to reduce interprocessor communication. Firstly, computation and data decomposition are mapped onto virtual processors, and the data decomposition pattern is analyzed to minimize the cost of data reorganization communication. By using the data decomposition pattern, the mapping of virtual processors to physical processor is determined. According to our experimental results, for non-uniform dependence loops, which have complex array subscripts and data access order has no data locality, they can be executed with less iterprocessor communication overhead on the distributed shared memory multiprocessors system if our method is applied. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#NT870392027 http://hdl.handle.net/11536/64048 |
显示于类别: | Thesis |