Study on High Performance Execution Scheme for Non-Numerical Computation Programs

非数值计算程序高性能执行方案研究

• 批准号: 13680413
• 负责人: SHIBAYAMA Kiyoshi
• 金额: $ 0.9万
• 依托单位: Kyoto Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680413/
• 关键词: Processor Architecture; Execution Control; Nun-Numerical Processing; Paralled Processing; Firmware; Profiling; Computer Architecture

We have developed the next-generation microprocessor architecture which achieves high performance comptutation for programs in non-numerical processing fields. In these programs, not only array structures are used, but also linked list structures are frequently used in order to implement several types of abstract data structures. Automatic parallelization techniques have been well studied for loops which access only to array structures, but complex linked list structure takes it very hard to parallelize programs efficiently. And so, this is a main obstacle to high-speed execution of programs.First of all, we had developed an efficient data preloading/prefetching mechanism for linear linked list structures, and extended and generalized this mechanism into new parallel execution scheme. In this scheme, linked list structures can be applicable to the parallelization in the same manner as array structures. Through this scheme, many codes which could not be parallelized can be executed efficiently in parallel on a multithreaded processor or a parallel computer.Our next step was to develop a scheme which search a part of codes for the parallelization. In conventional parallelization strategies, the most inner loop is generally parallelized. But for complex data structures which are combined from several types of linked lists or arrays, such conventional strategies are not always effective, and in many cases, they are iuaeffective. Our solution to this issue is to introduce a small size of control thread as firmware. This thread (which may be executed in parallel with application programs on a multithreaded processor, and may also be executed as an interrupt handier) dynamically profiles the execution of application programs, and chooses the most effective parallelization part among ones which are extracted and marked by the compiler.

我们开发了下一代微处理器架构，可以实现非数值处理领域程序的高性能计算。在这些程序中，不仅使用数组结构，还经常使用链表结构来实现几种类型的抽象数据结构。对于仅访问数组结构的循环，自动并行化技术已经得到了很好的研究，但复杂的链表结构很难有效地并行化程序。因此，这是程序高速执行的主要障碍。首先，我们为线性链表结构开发了一种高效的数据预加载/预取机制，并将该机制扩展和推广到新的并行执行方案中。在该方案中，链表结构可以以与数组结构相同的方式应用于并行化。通过该方案，许多无法并行化的代码可以在多线程处理器或并行计算机上高效地并行执行。我们的下一步是开发一种方案，搜索部分代码以进行并行化。在传统的并行化策略中，最内层循环通常是并行化的。但对于由多种类型的链表或数组组合而成的复杂数据结构，这种传统策略并不总是有效，而且在很多情况下，它们是无效的。我们解决这个问题的方法是引入一个小尺寸的控制线程作为固件。该线程（可以与多线程处理器上的应用程序并行执行，也可以作为中断处理程序执行）动态地分析应用程序的执行，并在编译器提取和标记的并行部分中选择最有效的并行部分。

项目成果

布目 淳: "超並列計算機向き負荷量予測型動的負荷分散方式の改良"情報処理学会 論文誌. 42・5. 1282-1285 (2001)

Jun Nunome：“大规模并行计算机的负载预测动态负载平衡方法的改进”日本信息处理学会杂志 42・5（2001）。

Atsushi Nunome: "An Improvement of Dynamic Load Balancing Scheme with Load Prediction Mechanism for Massively Parallel Computers"IPSJ Transactions. VOL.42, NO.5. l282-1285 (2001)

Atsushi Nunome：“针对大规模并行计算机的具有负载预测机制的动态负载平衡方案的改进”IPSJ Transactions。

岡崎 裕之: "ペアリングを用いたグループ署名に関する二,三の考察"電子情報通信学会 技術研究報告. ISEC2002-64. 53-60 (2002)

Hiroyuki Okazaki：“关于使用配对的组签名的一些考虑”IEICE 技术研究报告 53-60 (2002)。

Hiroyuki Okazaki,: "Notes on Group Signature Schemes with Pairing over Elliptic Curves."Technical Report of IEICE. C20O2-64. 53-60 (2002)

Hiroyuki Okazaki，：“关于椭圆曲线配对的群签名方案的注释”。IEICE 的技术报告。

Shuji Yamamura: "Evaluation of a Data Preload Mechanism for a Linked List Structure"Systems and Computers in Japan, Wiley. 33・3. 21-30 (2002)

Shuji Yamamura：“链表结构的数据预加载机制的评估”，日本系统和计算机，Wiley 33・3 (2002)。