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

在研究了可用于开发由数千个处理器组成的大规模并行计算机系统的互连网络的要求之后，我们确信树结构是最有前途的结构之一。虽然肥树在CM-5中已经很有名了，但肥树最重要的非阻塞特性在这里被忽略了。因此，我们研究了实现全脂树需要解决的问题，并提出了一种减少路由器中交换机数量的新方案。在现场可编程门阵列器件上研制了由4个处理单元和2个路由器组成的胖树机样机，对其性能进行了评价。数据传输速率达到了兆位/秒，证明了该元件可以应用于实际规模的互连网络。(2)作为竞争处理器算法的典型应用，本文研究了自动布线问题的并行求解。虽然竞争的处理器算法获得了相当令人满意的加速，但解决方案的质量，即布线速率低于传统的顺序路由器。因此，如何通过并行计算来提高解的质量就是问题所在。我们在竞争的处理器布线算法中加入了拆解过程，并在布线速率上取得了显著的提高。然而，拆解过程导致计算时间大大增加，并导致了多针网络问题。多引脚网是一组连接在引脚上的导线。如果这个网络被斯坦纳树（Steiner tree）所取代，斯坦纳树是一组连接在引脚和导线上的导线，那么布线速度有望得到显著提高。我们开发了从多针网络构造斯坦纳树的基本并行算法。(3)继续研究竞争处理器算法在手写体汉字识别中的应用。本学年建立了具有代表性的30个汉字汉字模式知识库，并进行了识别实验。本实验首先利用汉字结构分析器对ETL8B汉字特许模式数据库中的汉字模式进行分析，并将提取的汉字结构特征提供给代表不同汉字类别的30个智能体，这些智能体同时利用知识库找到每个笔画的对应关系，然后尝试将所呈现的笔画特征与各自数据库中的笔画特征进行匹配。如果不止一个代理认识到所呈现的模式属于他们的类别，就会发生冲突。处于冲突中的智能体相互比较他们在推理中使用过或没有使用过的规则，使用知识最深的智能体获胜。在这个实验中，我们获得了接近98%的识别率，这是非常令人满意的。少

(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