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

(1)为了将遗传算法应用于实际优化问题，研究了可在SIMD机器上高效实现的遗传算法大规模并行模型。该模型的第一个候选者，耕作模型，使用一组个体，这些个体不像众所周知的岛屿模型那样彼此交换个体，而是将群体中最好的个体与大师交换。因此，最优秀的个体被迅速分配给所有群体。通过在多层中堆叠主机集合和个体组的副本，很容易开发出分层大规模并行系统。为了将该模型在FPGA芯片上实现为一台SIAD机器，我们使用硬件描述语言VHDL语言对机器的主要部件进行了设计。(2)为了继续提高并行度，选择大规模并行遗传算法模型作为第二候选。在此模型中，每个组件…更多的人将邻居中任意的个体进行交叉和选择。通过仿真验证了该模型的收敛性能。为了在SIMD机器上实现该算法，每个处理单元被分配给每个个体，并且这些处理单元需要非常频繁地彼此通信。因此，互连网络的性能变得非常重要。我们设计了一个高速路由器作为开发高性能互连网络的关键部件。(3)SIMD机的最大特点是结构简单，可以将多个处理单元集成在一块VLSI芯片上。然而，众所周知，SIMD机器的编程灵活性非常差，因此它仅用于有限的应用。特别是遗传算法等搜索程序，在SIMD机上运行比较困难。另一方面，MIMD机的编程非常灵活，因为它可以使用与顺序编程非常相似的SPMD(单程序多数据)范例。如果SIMD机器能够运行SPMD程序，SIMD机器无疑将优于所有并行机。我们已经研究了一种实现这一目标的方法，并开发了一种新的分支机制，可以添加到传统的SIMD机器上。对该机制进行了明确的定义，设计了控制处理器和处理单元。当假设在这台机器上运行搜索程序时，观察到计算速度显著提高。较少

(1) In order to apply the genetic algorithm to real-scale practical optimization problems, the massively parallel model of genetic algorithm that can be efficiently implemented on a SIMD machine is investigated. The first candidate of the model, the farming model, uses a set of groups of individuals that do not exchange individuals each other as the well-known island model does, but exchange the best individual of the group with a master. Thus the most excellent individual is distributed to all groups rapidly. By piling up the duplicates of set of master and groups of individuals in a multilevel layr, the hierarchical massively parallel system is easily developed. To implement this model on FPGA chip as a SIAD machine, we have designed the principal elements of the machine by using the hardware description language VHDL.(2) Intending to still increase the degree of parallelism, the massively parallel genetic algorithm model is selected as the second candidate. In this model, each indiv … More idual takes the arbitrary individuals in the neighbor for the cross-over and the selection. The convergence of this model was confirmed by thorough simulation. To implement this algorithm on a SIMD machine, each processing element is assigned to each one of the individuals and those processing elements need to communicate with each other very frequently. Therefore the performance of interconnection network becomes very important. We have designed a high-speed router as a key element to develop the high-performance interconnection network to be used in this machine.(3) The great feature of the SIMD machine is that many processing elements can be integrated on a single VLSI chip because of its simple structure. However, the programming flexibility of SIMD machine is known to be very poor so that it is used only for limited applications. Particularly, the searching programs such as that of genetic algorithm, is considered difficult to run on SIMD machine. On the other hand, the programming of MIMD machine is very flexible as it can use SPMD (single program multiple data) paradigm which is very akin to the sequential program. Should the SIMD machine can run the SPMD programs, the SIMD machine will be undoubtedly superior of all aprallel machine. We have investigated to find a way to this goal and have developed a new branching mechanism that can be added to the conventional SIMD machines. We have defined this mechanism clearly and designed the control processor as well as the processing element. Significant improvement in computational speed was observed when a searching program is assumed to be run on this machine. Less