分布式状态空间生成的设计与实现  

Design and implementation of distributed state space generation

作　　者：郑霄[1,2] 李宏亮[1] 吴东[1] 原昊[1] 

机构地区：[1]江南计算技术研究所,江苏无锡214083 [2]解放军信息工程大学,郑州450002

出　　处：《计算机工程与应用》2009年第32期27-30,68,共5页Computer Engineering and Applications

基　　金：国家重点基础研究发展规划(973)No.2007CB310900;国家高技术研究发展计划(863)No.2007AA01Z117~~

摘　　要：状态空间生成的并行化是针对状态空间爆炸问题而提出的一种重要手段。提出了一种基于MapReduce的分布式状态空间生成方案,与现有的同类研究相比,它无需用户关心生成算法的并行化,具有简单易用性;与常规的MapReduce的用法相比,它增加了输入文件的自动生成和作业运行的自动循环控制。该方案已在小规模分布式环境下实现,实验结果表明:(1)基于Map-Reduce的分布式状态空间生成算法可以扩大模型的可求解规模;(2)对于状态空间规模的增长主要由托肯(token)数增加引起的一类模型,该算法具有良好的适应性和可扩展性。Parallelization of state space generation is an important technical method to deal with the state space explosion problem.A practical approach based on MapReduee framework is presented.It has the virtues of simpleness and easiness to use,which let the user need not earing about how to parallelize the state space generation algorithm,and that is where it differs from the existing distributed state space generation algorithms.Meanwhile,the manner that the MapReduee framework is used in this approach is also different from the common ones：It has the abilities of dynamically generating input flies and repeatedly executing the state space generation process in need,while the common use of MapReduce is to one-off process vast amounts of data in-paralleLThis approach has been implemented in a small-scale distributed environment and the experimental results show that： （I）distributed state space generation based on MapReduce does have the ability to analyze a model with large state space,and that （2）this method is quite applicable and sealable for a model with an increasing token number and a fixed place number, whose state spaee scales up mainly with the token number.

关 键 词：状态空间模型 分布式状态空间生成 MAPREDUCE HADOOP 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]