论文部分内容阅读
随着芯片集成度的不断提高和用户对电子产品功能更高的需求,基于共享存储器的异构多处理器片上系统(Multi-Processor System on Chip)逐渐成为高端嵌入式应用市场的主流。对于一个复杂的MPSoC系统,并行任务之间的互斥已经成为需高效解决的关键问题。另一方面,在我们的数字视频服务器项目中,所采用的平台是Davinci TMS320DM6446,该平台是一款典型的共享存储器异构多处理器片上系统,它集成了ARM和DSP两种不同的体系结构。为确保ARM和DSP对共享资源的访问正确性与并行性,互斥便成为一个不可回避、需高效解决的问题。本课题研究基于该体系结构的互斥机制,因而具有一定的理论和实际意义。本文对互斥模型、算法、实现等问题进行了较深入研究,主要工作如下:1.提出了一种共享存储器多处理器系统中的互斥模型。针对传统互斥模型不能很好地用于描述区分任务处理器源互斥算法等不足,提出了一种共享存储器多处理器系统中的互斥模型,该模型扩展了原有模型的定义和定理;精确量化了性能指标与互斥算法属性,能够适应更多互斥算法的描述、证明和性能衡量需求。2.在AK算法的基础上,针对共享存储器异构MPSoC,提出了三种基于优先级树的退避软互斥算法。针对AK算法所需共享空间为O(n)等缺点,本文提出了基于优先级树的退避软互斥算法(PTB: Priority Tree Backoff),该算法折衷考虑了实时性和公平性、共享空间复杂度仅为O(1),并且该算法更加易于实现。在激烈的临界区竞争情况下,AK和PTB算法均会造成很大的片上网络或总线交通量。鉴于此,本文提出了二次竞争PTB算法(TCPTB: Twice Competition Priority Tree Backoff),该算法既可以充分利用单处理器Cache一致性等资源,又可减少共享存储空间以及交通量、降低全局互斥算法设计复杂度。针对某些数据库和实时任务,在一定期限内未能进入临界区,则放弃临界区申请的需求,本文提出了可退出型PTB算法(APTB: Abortable Priority Tree Backoff),使得在最后期限仍未进入临界区的任务即时放弃临界区。3.设计并实现了基于Davinci DM6446平台的互斥中间件。为实现ARM与DSP任务间的高效互斥、并且为了真实比较算法性能优劣,需要在Davinci DM6446上实现各种互斥算法(因为仿真工具不够成熟和不对外开放)。同时,为了加强扩展性与通用性,本文将共享存储器管理、各种互斥算法实现、应用程序接口综合在一起设计了互斥中间件,并在Davinci DM6446上实现。4.实验比较及性能分析、总结。为衡量算法性能,本文采取真实实验平台做实验的方式进行评价,采用互斥模型中量化的性能指标。实验表明:在中、小规模临界区竞争情况下PTB算法效率优于AK算法;TCPTB算法在中、大规模的临界区竞争情况下效率高于AK算法;而APTB则考虑了某些实时任务和数据库任务在最后期限未能进入临界区而放弃申请的需求;以上三种算法与AK算法相比,仅需要很小的共享存储空间,能使实时任务优先进入临界区。