L系统的并行化关键技术
|
摘要
为解决L系统文法在字符迭代过程中生成效率低下的问题,提出一种基于并行框架的分解算法。通过L系统的文法特征将L系统进行分类,将分类后的文法字符进行多线程处理,提高文法的生成效率。可直接操作纯文本的L文法字符串,无需任何编译、链接翻译过程。实验结果表明,该算法可以高效处理参数化L系统、上下文敏感L系统和随机化L系统,当文法数量达到百万级规模时,算法生成文法的效率提高了25%。
To deal with the problem of low efficiency during the process of the character iterations under L-system,a deformation algorithm based on paralyzed frame was proposed.The L-system was classified through the grammar characteristics of the L-system,and the grammar characters were multithreaded after classification,thus improving the efficiency of grammar generation.Pure text of L-grammar was operated directly without building,linking and translating.The results show that the proposed method can solve parametric L-system,context sensitive L-system,and stochastic L-system with high efficiency,when the number of grammars of the algorithm reaches the million level,the efficiency of grammar generation is increased by 25%.
To deal with the problem of low efficiency during the process of the character iterations under L-system,a deformation algorithm based on paralyzed frame was proposed.The L-system was classified through the grammar characteristics of the L-system,and the grammar characters were multithreaded after classification,thus improving the efficiency of grammar generation.Pure text of L-grammar was operated directly without building,linking and translating.The results show that the proposed method can solve parametric L-system,context sensitive L-system,and stochastic L-system with high efficiency,when the number of grammars of the algorithm reaches the million level,the efficiency of grammar generation is increased by 25%.
引文
[1]SUN Minqi.Application of instantiation method in the modeling of L-System trees[J].Technology Communication,2013,5(16):227(in Chinese).[孙敏祺.实例化方法在L-System树木建模中的应用[J].科技传播,2013,5(16):227.]
[2]CHEN Hong,LIAN Sisi,WENG Qiyong,et al.Research on the construction method of Web 3Dorchard based on L-System model[J].Chinese Agronomy Report,2015,31(12):285-290(in Chinese).[陈宏,连思思,翁启勇,等.基于L-System模型的Web三维果园构建方法研究[J].中国农学通报,2015,31(12):285-290.]
[3]Liu Ziping,Xia Qixiao,Yu Yue.Simulation of tree and its swaying with wind generated by L-system[J].Computer Aided Drafting,Design and Manufacturing,2017,27(1):15-21.
[4]GAO Yang,LI Zhongrong,WEI Wei,et al.Research on modeling method of banyan based on parameter L-system[J].Computer Technology and Development,2016,26(7):156-159(in Chinese).[高扬,黎展荣,魏为,等.基于参数L系统的小叶榕树建模方法研究[J].计算机技术与发展,2016,26(7):156-159.]
[5]PEI Wentong,ZHU Jingfu.The 2D geometric modeling of soybean blades with B-spline curve and LS grammar[J].Jiangsu Agricultural Science,2016,44(1):411-414(in Chinese).[裴文彤,朱景福.结合B样条曲线与LS文法的大豆叶片二维几何建模[J].江苏农业科学,2016,44(1):411-414.]
[6]Santa FM,Ariza HM,Sarmiento FM.Fractal design approach for heat sinks using L-systems[J].Contemporary Engineering Sciences,2017,10(32):1551-1559.
[7]YANG Le.Construction and visualization of rice root model based on L-system[J].Technology Bulletin,2017,33(5):156-158(in Chinese).[杨乐.基于L系统的水稻根系模型构建及可视化研究[J].科技通报,2017,33(5):156-158.]
[8]WU Xiang,GAO Xiaoyang,SHAO Shilu,et al.Study on the growth visualization of grape fruit trees based on parameter L-system[J].Journal of Chinese Agricultural Machinery,2017,38(5):63-68(in Chinese).[吴翔,高晓阳,邵世禄,等.基于参数L系统的葡萄果枝生长可视化研究[J].中国农机化学报,2017,38(5):63-68.]
[9]Zhang S,Zhu Q,Liu J,et al.Parallel interpretation of L-system based on CUDA[J].Journal of Computational Information Systems,2013,9(2):415-424.
[10]Fridenfalk M.Application for real-time generation of virtual3Dworlds based on L-system[C]//International Conference on Cyberworlds.IEEE,2015:73-78.
[11]MIN Fang,ZHANG Zhixian,ZHANG Yujie.Research on multi-GPU parallel computing in virtualized environment[J].Microelectronics and Computer,2016,33(3):69-75(in Chinese).[闵芳,张志先,张玉洁.虚拟化环境下多GPU并行计算研究[J].微电子学与计算机,2016,33(3):69-75.]
[12]Bakhoda A,Yuan GL,Fung WWL,et al.Analyzing CUDAworkloads using a detailed GPU simulator[C]//IEEE International Symposium on Performance Analysis of Systems and Software.IEEE Xplore,2017:163-174.
[13]WEI Jian,James,WU Chehui.Automatic load balancing of3Dgraphics pipeline[P].CN:CN 101578629,2013(in Chinese).[魏建,詹姆斯,吴车辉.三维图形管线的自动负载平衡[P].CN:CN 101578629,2013.]
[2]CHEN Hong,LIAN Sisi,WENG Qiyong,et al.Research on the construction method of Web 3Dorchard based on L-System model[J].Chinese Agronomy Report,2015,31(12):285-290(in Chinese).[陈宏,连思思,翁启勇,等.基于L-System模型的Web三维果园构建方法研究[J].中国农学通报,2015,31(12):285-290.]
[3]Liu Ziping,Xia Qixiao,Yu Yue.Simulation of tree and its swaying with wind generated by L-system[J].Computer Aided Drafting,Design and Manufacturing,2017,27(1):15-21.
[4]GAO Yang,LI Zhongrong,WEI Wei,et al.Research on modeling method of banyan based on parameter L-system[J].Computer Technology and Development,2016,26(7):156-159(in Chinese).[高扬,黎展荣,魏为,等.基于参数L系统的小叶榕树建模方法研究[J].计算机技术与发展,2016,26(7):156-159.]
[5]PEI Wentong,ZHU Jingfu.The 2D geometric modeling of soybean blades with B-spline curve and LS grammar[J].Jiangsu Agricultural Science,2016,44(1):411-414(in Chinese).[裴文彤,朱景福.结合B样条曲线与LS文法的大豆叶片二维几何建模[J].江苏农业科学,2016,44(1):411-414.]
[6]Santa FM,Ariza HM,Sarmiento FM.Fractal design approach for heat sinks using L-systems[J].Contemporary Engineering Sciences,2017,10(32):1551-1559.
[7]YANG Le.Construction and visualization of rice root model based on L-system[J].Technology Bulletin,2017,33(5):156-158(in Chinese).[杨乐.基于L系统的水稻根系模型构建及可视化研究[J].科技通报,2017,33(5):156-158.]
[8]WU Xiang,GAO Xiaoyang,SHAO Shilu,et al.Study on the growth visualization of grape fruit trees based on parameter L-system[J].Journal of Chinese Agricultural Machinery,2017,38(5):63-68(in Chinese).[吴翔,高晓阳,邵世禄,等.基于参数L系统的葡萄果枝生长可视化研究[J].中国农机化学报,2017,38(5):63-68.]
[9]Zhang S,Zhu Q,Liu J,et al.Parallel interpretation of L-system based on CUDA[J].Journal of Computational Information Systems,2013,9(2):415-424.
[10]Fridenfalk M.Application for real-time generation of virtual3Dworlds based on L-system[C]//International Conference on Cyberworlds.IEEE,2015:73-78.
[11]MIN Fang,ZHANG Zhixian,ZHANG Yujie.Research on multi-GPU parallel computing in virtualized environment[J].Microelectronics and Computer,2016,33(3):69-75(in Chinese).[闵芳,张志先,张玉洁.虚拟化环境下多GPU并行计算研究[J].微电子学与计算机,2016,33(3):69-75.]
[12]Bakhoda A,Yuan GL,Fung WWL,et al.Analyzing CUDAworkloads using a detailed GPU simulator[C]//IEEE International Symposium on Performance Analysis of Systems and Software.IEEE Xplore,2017:163-174.
[13]WEI Jian,James,WU Chehui.Automatic load balancing of3Dgraphics pipeline[P].CN:CN 101578629,2013(in Chinese).[魏建,詹姆斯,吴车辉.三维图形管线的自动负载平衡[P].CN:CN 101578629,2013.]