这是对走向GPGPU JSON解析的一些后续内容。这提出了一种相当迂回的方法来并行化简单的解析任务。我有更多的GPU编程经验，我并不期望这种特定的方法能很好地工作，但它确实表明问题中存在并行性。
这篇帖子是一个新想法的写法，但请注意，没有实施。它可能包含一些错误，也许这个想法是有缺陷的。但如果它能坚持下去，我认为这是一条关于如何将顺序算法移植到GPU上的令人兴奋的研究路线。
对于这篇文章，我将提出这个问题的一个更简单的版本：对于每个左方括号，在解析树中记录父级的索引，对于每个右方括号，记录相应的左方括号的索引。
STACK=[NONE]对于i，输入中的TOKEN：RESULT[I]=STACK[len(STACK)-1]如果TOKEN=='；['；：STACK。PUSH(I)Elif Token=='；]'；：堆栈。POP()。
要遵循JSON POST中的运行示例，假设输入为[[][[]]。结果是：
索引0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17输入[[][[][]][][]]值-0 1 0 3 4 3 6 3 8 9 8 3 0 13 0 15 0。
它能被并行化吗？由于存在对以前状态的依赖关系，因此很难了解它是如何实现的。此外，状态本身的大小是无限的。它可以是O(N)；病理情况是一百万个开括号，然后是一百万个闭合。在实践中，根据工作负载的不同，我们可能会期望更适度的嵌套深度，但理想情况下，我们希望有一种至少可以相当好地处理所有情况的算法。
也许我们能做点什么。对于我的博客(以及之前的“绳索科学”系列)的老读者来说，我尝试使用Monid也就不足为奇了。
所以让我们把这个顺序程序变成一个么半群。如果我有一个时间门户，我会及时向前看，并使用一些有进取心的博士生到那时已经使用的方便的自动化工具。但是，如果做不到这一点，我会在我的脑海里做这件事。
么半群基本上是一系列的POP，然后是一系列的推动。由于POP操作(在本例中)没有有效负载，它们可以简单地表示为计数。所以么半群就是对(n_pops，元素)。PUSH的原语是(0，[element])，POP的原语是(1，[])。么半群运算是：
定义组合(m1，m2)：n1，s1=m1n2，s2=m2，如果n2&>=len(S1)：return(n1+n2-len(S1)，s2)否则：return(n1，s1[：LEN(S1)-n2]+s2)。
在此么半群上运行扫描或广义前缀SUM将在堆栈顶部产生所需结果，即么半群中序列的最后一个元素。
我相信一个自动化的工具来翻译这些简单的顺序程序是可能的，并且在它的背后有一个理论，它解释了么半群做和不做的方式。某些组合是可能的，例如，您可以相当容易地扩展此想法，以便每个子级都知道其相对于其兄弟项的序列号。要做到这一点，可以混入“计数么半群”，这只是整数加法。
如果我们在堆栈深度上有一个界限，我们就设置得很好了。问题是无界的情况。我最初的想法是有一个包含(比方说大小为k)元素的窗口，每个遍将处理大小为k的堆栈的一部分。我认为这是可行的，但本质上它需要与堆栈深度成比例的若干遍，因此在最坏的情况下为O(n^2)。
我的新想法是保留单遍扫描，但使用专门构建的数据结构来表示堆栈。顶部是一个包含k个元素的窗口，然后是一个链表(或者可能是块的链表；老实说，我还没有研究过所有的含义，更不用说实际实现和进行性能测量了)。
合并操作尝试在窗口中适应新的组合序列(直到共享链接，它只能保留该链接)。但是如果它溢出，那么它必须进行分配，很可能使用原子凹凸分配器进入全局内存，就像在Piet-GPU中经常做的那样。
要进行真正的性能分析需要实现，但应该可以对此进行一些推理。
显然，如果堆叠深度较浅，性能会很好。调用链表的速率将取决于工作负载以及并行度模式。值得注意的是，如果扫描是按顺序运行的，那么链表操作总是很便宜的。这是因为使用链表时，么半群操作核心的串联是不对称的-当右边的序列很小时，左边的大序列很便宜，但反过来就不便宜了。当纯按顺序运行扫描时，右侧的单体始终最大大小为1。
而作为当前技术水平的扫描的解耦回看实现基本上是在大粒度下顺序运行的；它只是试图利用硬件在较小粒度上提供的尽可能多的并行性。即使嵌套极深，它也应该在扫描时构建并保留堆栈的链表，并为当前正在处理的问题部分提供相对较小的窗口。
对业绩持乐观态度还有另一个原因。虽然分区之间的通信带宽随窗口大小而增加，但对于分区内的处理而言，情况并不一定如此。暂时搁置实现高效GPU内核的相对挑战性问题(这必然会利用SIMD并行性)，考虑在更传统的多核CPU上运行的解耦回溯实现，其中每个线程都是顺序的。
基本上，第一遍运行传统的顺序堆栈算法，但修改为某些输入堆栈可能不可用。末尾是么半群，“n_pops”是发生次数的计数，序列包含推入该分区内的所有元素。
在解耦的回看阶段，发布此么半群以供右侧的分区使用，并且分区还计算左侧分区的聚合。此阶段的么半群操作的成本将与窗口的大小成正比，但请记住，聚合的数量比元素的数量少一个数量级。
最后，在第二次遍历元素时，再次运行堆栈算法，这一次，从解耦的回看阶段获得的聚合中，第一次遍历中丢失的元素可用。作为另一个潜在的优化，第二遍可能会“跳过”在第一遍中完全在分区内本地计算的子树，只在跨越分区边界的子树上执行工作。
因此，我的分析是，该算法的工作因子非常好，这意味着在64核处理器上，它可能会比单核顺序实现快64倍(显然是对所有其他使其具有挑战性的常见因素进行取模)。
正如我提到的，高效的GPU内核很可能是具有挑战性的，可能需要一些棘手的技术来利用SIMD(WARP)并行性，而不需要花费太多时间来计算Monoid组合，但它在多核情况下似乎工作得如此好的事实是一个令人鼓舞的迹象，表明高效的、完全经过GPU调优的实现是可能的。
我甚至比以前更确信在GPU上可以进行高效的解析。“栈么半群”有望成为表示解析栈的基本构建块，通常用于操作树形结构的数据。我不知道有任何关于这一点的表述，尽管它很可能存在于文学中的某个地方。
从相应的简单顺序程序自动生成么半群(如堆栈么半群)似乎是一个非常有前途的研究领域。如果我是一名教授(我不是)，一个博士生把它作为提案带给我，我会相当兴奋的。
这种探索的部分动机是为了在Piet-GPU中表示“剪辑堆栈”，这已被证明是一个有点棘手的问题；作为预处理步骤，我可能至少会在CPU上计算其中的一部分。但是，在GPU上完成所有的计算将非常有吸引力，而且非常符合Piet-GPU的精神，如果对嵌套深度没有人为限制，就更是如此。如果我真的实现了这一点，它无疑将是另一篇博客文章(包括定量测量)。
但在此期间，我很有兴趣看看其他人是否会接受这些想法。自从我的JSON帖子发表以来，人们对它的兴趣一直很小。我也想知道有没有已经出版但还没看过的文学作品。如果不是，对我来说，这似乎是一个非常丰富的矿脉。
(作为个人笔记，我要离开Twitter一段时间，可能很长一段时间，因为我发现社交媒体真的在消耗我的精力。与我联系跟进的最好方式是电子邮件。不过，我确实喜欢听到人们的声音！)