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

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

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.