Study of Massively Parallel Processing System using a Number of Competing Processors and Its implementation

多处理器大规模并行处理系统的研究及其实现

• 批准号: 03680033
• 负责人: TAKAHASHI Yoshizo
• 金额: $ 1.28万
• 依托单位: The University of TOKUSHIMA
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1991
• 资助国家: 日本
• 起止时间: 1991 至 1993
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-03680033/
• 关键词: massively parallel computer; parallel processing; competing processors; wire routing problem; character recognition; character structure knowledge; conflict resolution; multi-agent

(1) After having studied the requirements for the interconnection network that can be used to develop a massively parallel computer systems to be constructed from several thousands of processors, we are convinced that the fat-tree is one of the most promising architectures. Although fat-tree is already famous as it is used in CM-5, the most important non-blocking feature of the fat tree is dismissed there. Therefore we have investigated the problems to resolved to realize the complete fat tree, and introduced a new scheme in decreasing the number of switches in the router. A prototype fat tree machine consisting of 4 processing element and 2 routers, which is developed on field programmable gate array device, is built to evaluate the performance. The date transfer rate of several mega bytes per seconds is obtained, and convinced us the element could be employed for real scale interconnection network.(2) As a typical application of competing processor algorithm, the parallel solution of … More the automated wire-routing problem has been studied. Although quite satisfactory speedup is obtainable by the competing processor algorithm, the quality of the solution, that is, the wiring rate is less than the conventional sequential router. Therefore the problem is how to improved the quality of the solution by parallel computation. We have added the rip-up process to the competing processor wire routing algorithm, and obtained a significant improvement in the wiring rate. However, the rip-up procedure causes the increase in the computation time considerably, and we are led to the multipin net problem. Multipin net is a set of wires connected at the pin. If this net is replaced by the Steiner tree, which is a set of wires connected both at the pin and the wire, a significant improvement on the wiring rate is expected. We have developed the basic parallel algorithm for constructing a Steiner tree from the multipin network.(3) The study of applying the competing processor algorithm to the hand-written Kanji character recognition is continued. In this year the knowledgebase for 30 representative Kanji character patterns was built and the recognition experiment was performed. In this experiment a character pattern taken from the ETL8B Kanji charter pattern database are first analyzed by the character structure analyzer and the extracted structural features are presented to 30 agents representing different character categories, which simultaneously find correspondence of each strokes using knowledgebase, and then attempts to match the presented stroke features with those in their individual database. If more than one agents recognize that the presented pattern belongs to their category, the conflict takes place. The agents in conflict compare the rules they have used or not used in the reasoning with each other and the agent which has used the deepest knowledge wins. In this experiment we have obtained almost 98% of recognition rate which is quite satisfactory. Less

(1)在研究了可用于开发由数千个处理器构成的大规模并行计算机系统的互连网络的要求之后，我们确信胖树是最有前途的体系结构之一。虽然胖树在CM-5中已经很有名了，但胖树最重要的非阻塞特性在那里被忽略了。因此，我们研究了实现完全胖树需要解决的问题，并提出了一种减少路由器中交换机数量的新方案。在此基础上，设计了一个基于现场可编程门阵列器件的由4个处理单元和2个路由器组成的胖树机器样机，并对其性能进行了测试。数据传输速率达到每秒数兆字节，证明该元件可用于真实的规模互连网络。(2)作为竞争处理机算法的一个典型应用， ...更多信息 研究了自动布线问题。虽然相当令人满意的加速是通过竞争处理器算法，解决方案的质量，即布线率是小于传统的顺序路由器。因此，如何通过并行计算来提高解的质量是一个亟待解决的问题。我们在竞争处理器的布线算法中加入了撕裂过程，在布线率上得到了显著的提高。然而，rip-up过程会导致计算时间大大增加，并且我们会导致多针网络问题。多针网络是一组在针处连接的导线。如果这个网络被Steiner树所取代，Steiner树是一组在引脚和导线处连接的导线，预计布线率会有显着提高。我们已经开发了基本的并行算法，用于从多针网络构造Steiner树。(3)本文继续研究竞争处理机算法在手写汉字识别中的应用。在这一年中，建立了30个有代表性的汉字字符模式的知识库，并进行了识别实验。在本实验中，一个字符模式取自ETL 8B汉字宪章模式数据库，首先分析的字符结构分析器和提取的结构特征呈现给30个代理代表不同的字符类别，同时发现每个笔画的对应关系，使用知识库，然后尝试匹配呈现的笔画特征与那些在各自的数据库。如果多个智能体识别出所呈现的模式属于它们的类别，则冲突发生。冲突中的代理人比较他们在推理中使用或未使用的规则，使用最深知识的代理人获胜。在这个实验中，我们已经获得了近98%的识别率，这是相当令人满意的。少

项目成果

Y.Takahashi, M.Sano: "Parallel Computing with a Number of Competing Processors" Proc. of International Conference on Parallel Computing '91, London,1991. 339-346 (1992)

Y.Takahashi、M.Sano：“具有多个竞争处理器的并行计算”Proc。

Yoshizo Takahashi, Hitotoshi Murakami: "Conflict Resolution Procedure in Massively Parallel Multi-Agent Pattern Recognition Systems" ParCo'93 Proceedings. (to appear). (1994)

Yoshizo Takahashi、Hitotoshi Murakami：“大规模并行多智能体模式识别系统中的冲突解决程序”ParCo93 论文集。

Masahiko Sano, Yoshizo Takahashi: "Performance Evaluation of Parallel Wire-Routing on the Shared and the distributed Parallel Computers" Trans.IPSJ. Vol.33, No.1. 369-377. (1992)

Masahiko Sano、Yoshizo Takahashi：“共享和分布式并行计算机上并行布线的性能评估”Trans.IPSJ。

佐々木一陽,高橋義造: "画素の対応関係に基づく超並列処理向き手書き漢字認識" 電子情報通信学会.技術研究報告. PRU92-106. 29-36 (1993)

Kazuyo Sasaki、Yoshizo Takahashi：“基于像素对应的大规模并行处理的手写汉字识别” IEICE 29-36 (1993)。

Masahiko Sano, Yoshizo Takahashi: "Performance Comparison of the Shared and the Distributed Memory Multiprocessors with parallel Wire-Routing Problem." Proc.of Joint Symposium on Parallel Processing. 197-204 (1991)

Masahiko Sano、Yoshizo Takahashi：“具有并行布线问题的共享内存多处理器和分布式内存多处理器的性能比较”。