文章基本信息

标题：Development of an Algorithm for Extracting Parallelism and Pipeline Structure from Stream-based Processing flow with Spanning Tree
本地全文：下载
作者：Shinichi Yamagiwa ; Guyue Wang ; Koichi Wada 等
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2015
卷号：5
期号：1
页码：159-179
语种：English
出版社：International Journal of Networking and Computing
摘要：It is a fashion to use the manycore accelerators to promote the computing power in a computing platform. Especially GPU is one of the main series of the high performance computing, which is also employed by top supercomputers in the world. Programming methods on such accelerators includes development of control programs which accelerators executes to schedule the invocation of the acceleratorâ€™s kernel program. The kernel program needs to be written based on the stream computing paradigm. Connecting I/Os of the kernel programs, we can develop a large application. When we consider the processing flow as a directed graph, we can implement a GUI-based programming tool for the accelerators. It visualizes a pipeline-based processing flow. However, it is very hard to find a starting point of a complex processing flow. Moreover, although the processing pipeline include the potential parallelism, it is hard for the programmer to exploit it intuitively. This paper proposes an algorithm applying the spanning tree that mechanically exploits the parallelism and determines an execution order. To verify the algorithm, this paper performs evaluation with realistic applications. The algorithm exploits effectively the parallelism and construct the optimal pipeline processing flow.Â
其他摘要：It is a fashion to use the manycore accelerators to promote the computing power in a computing platform. Especially GPU is one of the main series of the high performance computing, which is also employed by top supercomputers in the world. Programming methods on such accelerators includes development of control programs which accelerators executes to schedule the invocation of the acceleratorâ€™s kernel program. The kernel program needs to be written based on the stream computing paradigm. Connecting I/Os of the kernel programs, we can develop a large application. When we consider the processing flow as a directed graph, we can implement a GUI-based programming tool for the accelerators. It visualizes a pipeline-based processing flow. However, it is very hard to find a starting point of a complex processing flow. Moreover, although the processing pipeline include the potential parallelism, it is hard for the programmer to exploit it intuitively. This paper proposes an algorithm applying the spanning tree that mechanically exploits the parallelism and determines an execution order. To verify the algorithm, this paper performs evaluation with realistic applications. The algorithm exploits effectively the parallelism and construct the optimal pipeline processing flow.Â
关键词：High Performance Computing;Stream Computing;GPUs;Caravela;Spanning Tree Algorithm