题目：众核处理器并行程序运行时环境的研究与实现

近年来，单芯片处理器的核数一直在持续增长，很大程度上提高了处理器的整体性能，而且正在往众核体系结构的方向发展。任务窃取作为多核和众核体系结构中进行负载均衡的方式，通过把并行程序划分为任务的形式，每个线程维持一个任务队列, 线程从本地队列获取并执行任务，并通过偷取其他线程的任务进行负载均衡。

现有任务窃取并发队列主要有两方面缺点：第一，队列的实现需要使用内存栅栏来保证算法的正确性，但内存栅栏的使用相对一般程序指令在现有体系结构下开销较大，第二，现有并发队列灵活性差，不能扩展支持其他的任务调度策略，而这些调度策略能有效提高特定算法的程序性能。本文在通过研究现有并发队列算法的基础上，提出两种新的队列设计算法，通过使用阻塞队列保证队列的灵活性，支持多种任务调度策略，通过对队列访问策略进行优化，降低同步操作的开销。通过实验与现有并发队列进行性能对比，证明新的队列算法的有效性，能有效提高队列访问的性能。

针对随机任务窃取策略随着核数的增加，会增加核负载不均衡的可能性，性能扩展性效果逐渐降低。现在大多数对于共享内存系统下的任务窃取的研究，集中在任务窃取时如何调度优化任务，并提出了不同的优化策略，降低任务窃取开销等等，这些研究中都通过实时的在线profiling收集并行程序运行过程中信息来进行动态优化，并假设处理器核与核之间是等价关系，没有考虑到体系结构自身的特点，如内存，cache，处理器之间的互联关系，处理器核之间的通信延时，不能针对体系结构自身特点进行自适应优化。提出根据体系结构拓扑进行处理器资源的管理，并指导上层进行任务调度，分层任务窃取和线程组内任务线性探测结合的策略，对每次窃取操作提供指导，快速的获取任务，降低总体任务窃取次数，提高任务窃取的有效性。

实现了基于上述双端队列算法，资源管理，任务调度优化的运行时环境，并通过实验证明运行时环境能在众核体系结构下获得很好的性能。同时还在SDN网络控制器中加入运行时支持，使其支持细粒度的事件的并行，提高控制器对网络流的处理能力，能够控制更大规模的网络。