A Study on the Emergent Strategy Acquisition in the Massively Parallel Graph-Reduction

我们开发了一个交互式视觉模拟器来观察紧急计算模型的复杂行为。作为使用该模拟器的初步实验，我们尝试在奖励矩阵上定义的多智能体博弈中生成合作策略。由于意外计算的本质是偶然性，因此在多智能体博弈中识别意外行为并不容易。此外，指定代理的参数非常关键。我们已经尝试在上面描述的视觉模拟器上为lambda表达式构建一个大规模并行图形缩减系统。为每个智能体设计局部转换规则是一项比我们想象的要困难的工作。因此，在实际的仿真步骤中，我们无法在使用协作代理的图约简过程中发现有趣的突发行为。因此，我们在一定程度上改变了原来的研究计划，并开发了一个紧急负载平衡系统，用于大规模并行图缩减。在大规模并行计算领域，自主代理（计算节点）在其邻居中搜索负载较轻的节点，以转移额外的任务。为了将随机学习自动机应用于遗传算法的适应度评估，我们实现了在动态变化的负载环境下的高度自适应负载平衡。我们在大规模并行计算机SR2201上实现了紧急负载平衡系统的原型。通过使用无文件访问的独立虚拟任务，我们发现并行计算领域出现了良好的负载均衡。任务传递的节点簇以自组织的方式构建。这是紧急计算模型的一个显著特征。大规模并行计算领域的负载均衡是紧急计算的重要应用之一。

We have developed an interactive visual simulator for observing complex behavior of the emergent computation model. As a preliminary experiment using this simulator, we have tried to generate cooperative strategies in a multiagent game defined on a reward matrix. It is not so easy to identify emergent behavior in the multiagent game because of the accidental property that is the essence of the emergent computation. Moreover the parameters specifying the agents are very critical.We have tried to build a massively parallel graph-reduction system for lambda expressions on the visual simulator described above. To design the local transition rules for each agent is a harder work than we expected. Consequently, within the practical simulation steps, we could not find out interesting emergent behavior in the graph-reduction process by using the cooperative agents. Hence, we have partially changed our original research plan, and developed an emergent load balancing system for the massively parallel graph-reduction. In a massively parallel computation field, an autonomous agent (computation node) searches lightly-loaded nodes among its neighbors to transfer extra tasks. To apply a stochastic learning automaton to the fitness evaluation in a genetic algorithm, we have achieved highly adaptive load balancing with a dynamically changing load environment.We have implemented a prototype of the emergent load balancing system on the massively parallel computer SR2201. By using independent virtual tasks with no file access, we have found well load balancing emerged in the parallel computation field. Clusters of nodes for the task transfer is built up in a self-organized way. This is a distinguished feature of the emergent computation model. The load balancing in the massively parallel computation field is one of the promising applications of the emergent computation.