通过位平面编码和按位向量化提升元胞自动机性能

《Parallel Computing》:Improving cellular automata performance with bit-planes encoding and bitwise vectorization

【字体: 大 中 小 】 时间:2026年09月27日 来源:Parallel Computing 1.1

编辑推荐:

   •提出的位平面数据编码方法能够实现高效的位向量操作。•通过优化的CUDA实现,达到了两个数量级的加速比。•使用10种不同的元胞自动机展示了该方法的多功能性。•将该方法作为开源Cellato框架的扩展进行了实现。引言元胞自动机(CA)是一种离散计算模型,能够通过简单的局部规则模

  
  • •
    提出的位平面数据编码方法能够实现高效的位向量操作。
  • •
    通过优化的CUDA实现,达到了两个数量级的加速比。
  • •
    使用10种不同的元胞自动机展示了该方法的多功能性。
  • •
    将该方法作为开源Cellato框架的扩展进行了实现。

引言

元胞自动机(CA)是一种离散计算模型,能够通过简单的局部规则模拟复杂系统。它由一个单元格网格组成,每个单元格处于有限个状态之一,并根据基于相邻单元格状态的一组规则,在离散时间步上进化。CA已广泛应用于物理、生物学和计算机科学等多个领域,用于模拟流体动力学、种群增长和模式形成等现象 [1], [2], [3]。
尽管CA主要因其可视化复杂系统并有助于更好地理解这些系统的能力而受到称赞,但某些类型的模拟,如交通模型 [4] 或电路 [5],也需要高性能处理才能在实际中使用。幸运的是,典型的CA是模板计算(stencil computations)的特殊(离散)情况,非常适合并行化(即使在使用的加速器如GPU上也是如此),并且许多优化已经为它们而设计。另一方面,CA尚未从性能角度得到深入研究,这留下了改进的空间。
除了优化CA计算性能带来的直接影响外,这些算法作为研究并行计算和向量化各个方面的潜在候选对象也很有趣。CA规则通常易于计算,因此性能往往受限于内存带宽。此外,大多数CA只使用有限数量的状态,这允许实验各种数据布局和位打包技术,从而减少内存需求并提高数据传输效率。另一方面,专门的内存编码可能需要每个单元格的额外计算,这可能抵消减少内存流量的好处。因此,CA也是研究计算受限型和内存受限型工作负载之间权衡的一个有趣案例。
我们的工作受到Fujita等人[6]对康威生命游戏的位向量实现的启发。该方法每个单元格只需一个位,因此状态可以使用位操作进行并行处理。我们将这个想法扩展到支持具有更大状态空间的CA,其中网格以位平面形式存储(即每个编码状态的每个位对应一个数组)。此外,我们扩展了Cellato [7],这是一个基于模板的C++抽象,用于定义CA规则,它抽象掉了困难的实现细节(如位平面数据布局),使用户可以专注于CA逻辑。为了展示该方法的可行性,我们使用该技术(由CUDA加速并通过时间分块优化)实现了10种不同的CA,并进行了广泛的评估。所有测试的CA都显示出显著的性能改进;某些自动机甚至比其基线CUDA实现达到了两个数量级的加速比。
总之,本文的主要贡献如下:
  • •
    我们为具有多状态的CA提出了一种位平面数据布局,能够实现高效的位向量操作。
  • •
    我们扩展了Cellato框架以支持这种数据布局。
  • •
    我们为Cellato实现了一个CUDA后端,以支持在GPU上高效执行,包括已知的时间分块等优化。
  • •
    我们的方法通过实现10种不同的CA进行了评估,展示了其有效性,并总结了适用于类似数据并行离散问题的经验教训。
  • •
    我们对Cellato的修改、已实现的CA、实验结果以及相关复现脚本均在我们的开源复现包中提供,公开在GitHub上 [8]。
本文的组织结构如下。第2节提供元胞自动机的背景信息、已知的并行化和优化技术、Cellato抽象,并介绍我们在工作中使用的CA。基于位平面数据布局的CA规则位向量操作在第3节中介绍。第4节详细说明了需要解决的实现细节。第5节呈现了实验评估及其结果。第6节讨论相关工作,第7节总结全文。

章节摘要

背景

元胞自动机(CA)在一个规则的单元格网格上运行(通常为二维),每个单元格保持来自有限集合 S={s0,…,sk?1} 的离散状态。其计算以离散步(迭代)进行;在每一步中,所有单元格使用CA规则同时更新。更新规则可以表示为一个函数 f:S|N|→S,其中 N 是一个单元格的邻域。邻域通常是本地化的单元格组,被更新的单元格位于其中心。在二维网格的情况下,最

位向量操作

向量化是面向性能优化的重要组成部分。然而,典型的单指令多数据(SIMD)指令集(如SSE或AVX)专注于浮点或整数运算,而GPU架构(如CUDA)则更注重线程级并行性(通过轻量级线程和SIMT模型)。
CA规则通常很简单,基于逻辑操作,并且CA状态通常只需要几个位就能表示。从这个角度来看,传统的位指令(AND

实现

在定义了位向量操作和位平面编码的原则之后,我们现在讨论它们如何集成到Cellato框架[7]中。虽然可以使用所提出的网格和位向量抽象逐个实现每个元胞自动机(CA),但这种方法是重复的、容易出错的且耗时的。Cellato抽象的主要优势在于每个操作、位平面编码以及在CUDA中的并行网格处理都只需实现一次,

实验评估

所有实验均在配备80 GB设备内存的NVIDIA H100 GPU(计算能力9.0)上进行,服务器搭载AMD EPYC 9454 48核处理器,使用CUDA版本13.0,驱动程序版本580.82.07,操作系统为Rocky Linux。为确保公平比较,我们为所有实现(包括基线)执行了广泛的超参数网格搜索。这些参数汇总在表4中。
在网格搜索过程中,我们评估了若干超参数范围。对于

相关工作

模板计算和元胞自动机(CA)优化领域非常广泛。由于CA是模板计算的特殊情况,相关工作可以大致分为两类。第一类包括针对CA框架和特定CA优化的工作,第二类则聚焦于通用模板计算,这些也适用于CA。
在专用元胞自动机框架领域的工作相当有限。最显著的例子是Golly [24],这是一个灵活的,

结论

在本文中,我们介绍并评估了一种利用位向量操作加速元胞自动机模拟的新方法。通过将CA网格表示为位平面内存布局,我们的方法能够使用基本的位指令实现SIMD风格的向量处理。我们提出了这种布局的两种变体(线性和平铺),并将其作为通用后端集成到Cellato框架中,证明了高性能技术可以广泛适用而无需

CRediT作者贡献声明

Matyá? Brabec:撰写——初稿,软件,方法论,调查研究,概念化。Ji?í Klepl:撰写——审阅与编辑,验证,软件,调查研究。Martin Kruli?:撰写——审阅与编辑,指导,项目管理,资金获取。

生成式AI及AI辅助技术在稿件准备过程中的声明

在准备本工作的过程中,作者使用了Gemini、ChatGPT和Grammarly进行语法和风格检查,以及旨在使内容更清晰的简单文本转换。在使用这些工具后,作者对内容进行了审阅和编辑,并对已发表文章的内容承担全部责任。

利益冲突声明

作者声明以下财务利益/个人关系,这些可能被视为准潜在的利益冲突:Martin Krulis、Matyas Brabec、Jiri Klepl报告获得了Johannes Amos Comenius计划的资金支持。如果有其他作者,他们声明没有已知的竞争财务利益或个人关系可能影响本文所报告的工作。

致谢

本文得到了Johannes Amos Comenius计划(PJAC,自然和人为地质风险)项目CZ.02.01.01/00/22_008/0004605以及查理大学机构资助SVV(资助号260821)的支持。
Matyá? Brabec|Ji?í Klepl|Martin Kruli?
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号