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

(1)在研究了可用于开发由数千台处理机构成的大规模并行计算机系统的互连网络的需求之后，我们确信胖树是最有前途的体系结构之一。虽然胖子树在CM-5中的使用已经很有名了，但胖子树最重要的非阻塞特性在这里被忽略了。因此，我们研究了实现完全胖树需要解决的问题，并提出了一种减少路由器中交换机数量的新方案。在现场可编程门阵列器件上开发了一个由4个处理单元和2个路由器组成的胖树机器原型，并对其性能进行了评估。得到了几兆字节/秒的数据传输率，证明了该单元可以用于实际规模的互连网络。(2)作为竞争处理机算法的典型应用，…的并行解决方案此外，还对自动布线问题进行了研究。虽然竞争处理器算法可以获得令人满意的加速比，但解决方案的质量，即布线率低于传统的顺序路由器。因此，如何通过并行计算来提高解的质量就成了问题。我们在竞争的处理器布线算法中加入了撕裂工艺，在布线率上有了显著的提高。然而，撕裂过程导致了计算时间的显著增加，从而导致了多针网络问题。多引脚网络是在引脚处连接的一组导线。如果这个网络被斯坦纳树取代，这是一组同时在引脚和导线上连接的导线，布线率有望显著提高。我们开发了从多针网络构造Steiner树的基本并行算法。(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