非阻塞无等待数据并行调度器

摘要

描述了用于将数据并行任务调度到处理系统的多个线程执行单元上的方法、系统和介质。描述了无锁队列结构及操作方法的实施例以实现用于调度精细粒度数据并行任务以供在计算系统中执行的方法。多个工作者线程之一的工作相对于其它工作者线程是无等待的。队列的每个节点保存对可由多个线程执行单元并发地执行的任务的引用，但是每个任务是针对不同的数据子集执行的。多个实施例涉及在多线程计算平台上对数据并行任务的基于软件的调度，该多线程计算平台不在硬件中执行这种调度。也描述并要求保护其他的实施例。

主权项

一种系统，包括：处理系统，其具有多个线程执行单元；至少一个存储器元件，其耦合至所述线程执行单元中的一个或多个；以及调度逻辑，其使所述线程执行单元中的每一个并发地执行包括任务的指令集，每个任务是针对数据集的子集而执行的，其中所述调度逻辑包括存储在所述存储器元件中的一个或多个软件模块；所述调度逻辑进一步包括：用于执行使所述任务进入维持在所述存储器元件中的队列存储元件内的无锁入队操作的逻辑，其中所述任务包括多个工作项目，每个工作项目与所述子集之一相关联；以及用于通过多个工作者线程执行使所述工作项目离开队列以便在所述多个线程执行单元上并发地执行的并发无等待出队列操作的逻辑。