The Prospero Challenge

Matt Keeter，2025年3月

prospero.vm (https://www.mattkeeter.com/projects/prospero/https:/github.com/mkeeter/fidget/blob/main/models/prospero.vm) 是一个纯文本文件，包含 7866 个数学表达式。 它的开头如下所示：

# Text of a monologue from The Tempest
_0 const 2.95
_1 var-x
_2 const 8.13008
_3 mul _1 _2
_4 add _0 _3

...以此类推，持续了_很多_行。 如果使用 ±1 平方内的 (x,y) 值来评估表达式，然后根据其符号将像素着色为黑色或白色，您将得到以下图像：

text of a monologue from The Tempest, in black-on-white text

这个 "challenge" 非常简单：尽可能快地渲染图像。 一个基本的渲染器是 28 行 Python 代码，使用 Numpy 进行像素并行处理：

import numpy as np
with open('prospero.vm') as f:
  text = f.read().strip()
image_size = 1024
space = np.linspace(-1, 1, image_size)
(x, y) = np.meshgrid(space, -space)
v = {}
for line in text.split('\n'):
  if line.startswith('#'):
    continue
  [out, op, *args] = line.split()
  match op:
    case "var-x": v[out] = x
    case "var-y": v[out] = y
    case "const": v[out] = float(args[0])
    case "add": v[out] = v[args[0]] + v[args[1]]
    case "sub": v[out] = v[args[0]] - v[args[1]]
    case "mul": v[out] = v[args[0]] * v[args[1]]
    case "max": v[out] = np.maximum(v[args[0]], v[args[1]])
    case "min": v[out] = np.minimum(v[args[0]], v[args[1]])
    case "neg": v[out] = -v[args[0]]
    case "square": v[out] = v[args[0]] * v[args[0]]
    case "sqrt": v[out] = np.sqrt(v[args[0]])
    case _: raise Exception(f"unknown opcode '{op}'")
out = v[out]
with open('out.ppm', 'wb') as f: # write the image out
  f.write(f'P5\n{image_size} {image_size}\n255\n'.encode())
  f.write(((out < 0) * 255).astype(np.uint8).tobytes())

在我的机器上，这大约需要 15 秒 才能生成一个 1024×1024 的图像。 (剧透： 它还会为中间结果分配 60+ GB 的 RAM，因此请考虑在您自己的机器上运行它之前减小图像大小） “但是等等！”，您说。“还有很多明显的改进空间！您可以预先解析表达式，或者使用 numba，或者在 GPU 上运行它，或者使用 LLVM ...” 是的。 我希望你做这些事情，然后告诉我它们！ 此页面已添加了一些我的项目，但我希望它能发展到包含其他人不同的实验。 以下是一些需要思考的想法：

提交您的实验

请随时通过电子邮件发送成功和不成功的实验至 matt.j.keeter@gmail.com，我会将它们添加到此页面。 理想的提交内容是博客文章或代码仓库，以及您希望包含在此页面上的几句话描述。我也很乐意包含英雄图像或视频嵌入。 描述应指出任何特别有希望的结果、巧妙的想法或有趣的工具！不要_太过于_关注绝对速度；目标是探索想法，即使不打破任何性能记录也可以做到！

有奖品吗？

除了永恒的名声和荣耀？ 如果您提交一篇有趣的介绍，如果恰好我们在同一个城市，我会请您喝咖啡或饮料。Cambridge / Boston / Somerville 的居民尤其容易获得他们的奖品；我不保证来自更远地方的提交。

背景资料

Interval Arithmetic and Recursive Subdivision for Implicit Functions and Constructive Solid Geometry (Duff '92) 是对常用技术的绝佳介绍。特别是，区间算术、空间细分和表达式简化的组合仍然是现代渲染器的基础。 这些想法也在我的论文 §3.7 中提出，Hierarchical Volumetric Object Representations for Digital Fabrication Workflows (2013)，尽管我个人的实现自那时以来已经发展（请参见下面的示例）。 最后，我做了一个题为 Implicit Surfaces & Independent Research (2025) 的演讲，其中涵盖了所有这些材料，并且与我当前的实现非常接近。听众是 CS 专业大四学生，因此旨在易于理解！

Gallery

Massively Parallel Rendering of Complex Closed-Form Implicit Surfaces

Matt Keeter，2020

Paper homepage

MPR 实现将表达式编译为基于寄存器的字节码，然后使用在 CUDA 内核中运行的小型解释器执行它。解释器使用 区间算术 并行评估许多空间区域上的表达式，然后简化表达式，细分活动区域并递归。在小于特定大小的情况下，我们切换到逐像素评估，也并行在 GPU 上进行。

表达式简化对于性能尤其重要：到我们评估单个像素时，表达式缩小了 200 倍！

大部分艰苦的工作都用于将深度递归算法（每个分支中都有异构工作负载）转换为更易于 GPU 使用的东西。

使用 Tesla V100 渲染 1024×1024 图像需要 3.9 毫秒，这在 2020 年是高端 GPU（并且仍然非常强大）。性能在 4096×4096 时基本持平，表明对于这种 2D 渲染，我们远未饱和 GPU（本文还描述了 3D 渲染的类似策略）。

不幸的是，我没有设置时间的计时数字，但内核是通用解释器，即_不_专门针对特定表达式。

Fidget

Matt Keeter，2025

Project homepage

Fidget 使用相同的区间评估和表达式简化的广泛策略，但在 CPU 上运行并将表达式编译为具有 JIT 编译器的机器代码。

在 M1 Max CPU (2021) 上运行，它以 6.3 毫秒 渲染 1024×1024 图像，设置时间约为 11 毫秒：

$ cargo run -pfidget-cli --release -- render2d -i models/prospero.vm \
  -s1024 --eval=jit -N500 --mode mono
[2025-03-23T21:26:44Z INFO fidget_cli] Loaded file in 4.994333ms
[2025-03-23T21:26:44Z INFO fidget_cli] Built shape in 6.04525ms
[2025-03-23T21:26:47Z INFO fidget_cli] Rendered 500x at 6.331644 ms/frame

扩展到 4096×4096，需要 57 毫秒，大约慢了 9 倍；这是次线性缩放，因为它有 16 倍的像素。

这个项目有几个有趣的方面：

Prospero challenge, now with more garbage collection

Max Bernstein，2025

Blog post

Max 通过向 Python 解释器添加垃圾回收来解决“60 GB 中间结果”问题，从而实现了 4 倍的加速（并显着减少了 RAM 使用量，降至约 1 GB）。

这篇文章还展示了 CuPy，它是 Numpy 的直接替代品，可将计算卸载到 GPU。只需替换导入语句即可进一步加速 6.6 倍！

目前为止就这样；但您可以提交自己的实验来提供帮助！

© 2025 Matt Keeter