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.