用于多处理器核执行的编组机制

摘要

提供了一种用于在多核处理器上执行的并发编组操作。向编组操作提供元素的序列或组。在一个阶段，每个工作者都接收要被编组的元素序列的分区。将每个分区的元素布置成到包括一个或多个键的数据结构中，每个键都对应于与该键相关联的所接收的元素中的一个或多个的值列表。在另一阶段，合并由每个工作者创建的数据结构，使得整个元素序列的键和相应元素存在于一个数据结构中。递归合并可以以恒定时间完成，该时间与序列的长度不成比列。

主权项

一种用于对元素序列进行编组的方法，包括：接收元素序列的多个分区，其中多核处理器的可用核的每个都接收所述多个分区的单独的分区以用于处理；并发地将每个单独的分区编组成元素的至少一个值列表的键表，其中每个值列表中的元素都包括共同的键；以及将所述键表中的每个合并到一起以形成最终的键表，使得所有键以及它们的相应值列表都被包括在所述最终的键表中。