数据流程序动态调度与优化

为了解决数据流编程模型的可用性问题,使其能在兼顾程序并行性的前提下适用于动态数据交互速率的流应用,设计了一种动态调度与静态优化相结合的数据流编译系统。编译器以COStream语言编写的源程序为输入,通过对源程序进行分析,以动态速率的数据通信边作为边界划分程序到粗粒度的子图,在子图内部应用静态优化。根据子图的每个计算单元的工作量估计计算资源的使用状况,实现子图内计算单元到处理器核的映射,经过阶段划分分配子图内计算单元到相应流水阶段。在运行时,每个子图在各个处理器核上均启动一个线程,通过对线程间通信的优化,避免了运行时多个线程对同一段内存同时读写产生的同步开销,减少了线程的上下文切换次数。使用信号量控制子图内线程间的同步,基于各子图计算单元运行时数据交互速率并结合当前线程的状态,动态调度各个子图的执行,构建动态的软件流水线,生成相应多线程目标代码。实验以通用X86-64多核处理器作为实验平台,测试和分析数据流编译的性能。实验结果表明,编译系统可以实现动态数据交互速率的数据流应用,扩大了编译系统可用性并且具有一定加速效果。

Dynamic task scheduling and optimization of data flow program

In order to solve the availability problem of data flow programming models, which can be used for flow applications of dynamic data exchange rate under the premise of taking into account the parallelism of programs, we design and implement a dataflow compiling system which combines dynamic scheduling and static scheduling. The compiling system takes COStream programs as its input. It analyzes the program and uses communications with dynamic rate to divide stream applications into coarse-grained sub graphs. Then in sub graphs, static optimization is used. The system assigns the computing units of sub graphs to CPU cores based on the workload of each computing unit and the utilization of computing resources. After stage division, the system allocates each computing unit to its corresponding pipeline stage. At runtime, each sub graph starts a thread on each processor core. The optimization of communications between threads avoids the expenses of multiple threads’ reading or writing memory at the same time. We use semaphore to control the synchronization between threads and dynamically schedule each sub graph based on the dynamic rates of communications and the states of threads. Then we construct the software pipeline scheduling and create multi-thread codes. We choose common X86-64 as the experiment platform to test programs and analyze the results. Experimental results show that the compiling system can realize dynamic stream applications. It expands the usability of the system and increases the speedup.