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

(1)为了将遗传算法应用于实际优化问题，研究了可在SIMD机器上高效实现的遗传算法大规模并行模型。该模型的第一个候选模型是农业模型，它使用一组个体，这些个体不像众所周知的岛屿模型那样相互交换个体，而是将群体中最好的个体与主人交换。因此，最优秀的个人被迅速分配到所有群体。通过将主节点集和个体组的副本堆积在一个多层中，可以方便地构造出分层的大规模并行系统。为了在FPGA芯片上实现该模型作为SIAD机，我们使用硬件描述语言VHDL设计了机器的主要元素。(2)为了提高并行度，选择大规模并行遗传算法模型作为第二候选。在这个模型中，每个人 ...更多信息 idual将邻居中的任意个体用于交叉和选择。通过仿真验证了该模型的收敛性。为了在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