流应用在日常生活中有着广泛的应用,比如音频和视频编解码、软件无线电中的通信信号处理、图形图像处理和雷达信号处理等均属于流应用的范畴。随着用户对系统性能的要求日益增长,这些应用对平台计算能力的要求越来越高。比如,随着视频清晰度的增加,视频解码器需要更多的计算来满足特定速率要求。为了提供充足的计算能力并在功耗、设计成本等方面取得折中,流应用系统常采用多处理器片上系统来实现。由于流应用通常具有严格的实时性要求,如应用延时和/或吞吐量需要满足严格性能指标,因此分析应用在硬件平台上的调度性能对于确保系统性能至关重要。另外,系统性能与应用调度紧密相关,因此研究应用在硬件平台上的调度对于合理利用硬件资源、更好地满足系统性能需求有重要作用。本文围绕流应用在多处理器片上系统上的并行调度与性能分析展开深入研究,主要研究内容和成果如下。论文首先针对流应用在多处理器片上系统上的映射问题,提出了一种并发图模型来量化和建模应用任务间的并发性,设计了一种基于自同步调度的并发图构建算法,并将流应用的映射问题转换为并发图的分割问题。基于并发图,论文将流应用的映射问题建模为纯0-1整数线性规划模型。由于整数线性规划模型的复杂度随应用规模和处理器数目的增加而增加,不能有效应用于大规模问题,论文提出了一种由贪婪策略与精炼两个步骤组成的启发式算法,采用贪婪策略获取初始映射策略,然后采用任务迁移的方式逐步精炼映射的并发度。实验表明所提出的算法性能优于已有方法。针对流应用并行调度的吞吐量分析问题,论文提出了一种基于同构同步数据流图的调度感知同步数据流模型来建模周期静态顺序调度,同时提出了相应的建模方法。通过利用应用模型结构特征及周期静态顺序调度特征,减少了模型中的任务、边和初始符号数目;同时,可以使用已有分析方法对所提出的模型进行吞吐量分析。实验表明,所提出的建模方法优于已有方法,可以有效提高吞吐量分析效率。针对采用片上网络作为互联架构的多处理器系统,论文将任务复制和映射约束的任务与通信协同调度问题建模为整数线性规划模型,解决了流应用在特定约束下的最优调度问题。首先针对无通信竞争的调度问题,提出了一种无竞争整数线性规划模型。针对基于电路交换和静态路由策略的片上网络,对通信在片上网络上的调度进行建模;同时建模了任务在多处理器上的调度问题。在存在通信竞争的系统中,通信竞争对调度精确度有重要影响。为了提高调度精确度及模型的实用性,论文对无竞争整数线性规划模型进行扩展,提出了一种竞争感知的整数线性规划模型。通过在模型中增加约束条件,限制不同通信事务在通信路径上的竞争,确保所获得的通信调度不会产生竞争。实验表明所提出的整数线性规划模型能够有效地提高调度性能。论文最后针对配置有可预测内存架构的多处理器片上系统,提出了一种基于迭代的任务-缓存协同调度框架,解决了流应用的任务-缓存协同调度问题。流应用的不同任务通过缓存进行相互通信,应用的调度性能与缓存大小有重要关系,论文提出了基于状态空间分析及迭代策略来优化缓存大小的方法。硬件平台中不同内存块的大小不同,各处理器对不同内存块的访问速度也各不相同,因此缓存在内存中的分配与调度性能紧密相关。论文提出了全局缓存分配优化算法,通过优化全局缓存访问代价来优化缓存在内存子系统中的分配。为了对系统性能进行分析,论文提出了将任务调度和缓存调度建模到同步数据流图中的方法,并采用基于状态空间搜索的分析方法进行吞吐量分析。实验表明所提出的算法性能优于已有调度算法。