论文部分内容阅读
由于很多嵌入式系统是主要由电池提供能量,存储器的容量有限,且有实时性要求,因此,设计有效算法以优化能耗、空间及时间性能对嵌入式系统至关重要。对以上几个因素的优化可以显著提高系统性能。在这篇论文中,我们将探讨对化以上这几个因素的新技术和方法。特别地,对于能耗最优化问题,我们提出两种方法。第一种是基于在领域内被广泛研究的任务调度方法。我们从理论分析的角度研究了单处理器系统上任务调度的一种特殊情形,目标是优化处理器上消耗的能量。另一种减小能耗的方法是通过在系统中使用一种新型存储器—相变随机存储器(Phase Change Random Access Memory, PRAM)。与传统的存储器技术动态随机存储器(Dynamic Random Access Memory, DRAM)目比,PRAM的优点是优异的能耗特性,缺点是写操作次数有限。我们利用DRAM与PRAM组成混合存储器,在此存储器上研究了任务分配问题,目标是优化能耗和减少PRAM上的写次数以延长存储器寿命。为了优化存储器的时间和空间性能,我们研究了一种特别的嵌入式系统—流处理系统(Stream Processing System)。该系统在多媒体与科学计算中得到广泛应用。其中,流寄存器文件(Stream Register File, SRF)是系统中的关键资源。SRF的空间与数据传输时间是影响系统性能的两个重要因素。在这篇论文中,我们利用循环变换技术优化这两个因素以提高系统性能。本文主要关注嵌入式系统设计中的以下儿个热点问题:(1)利用任务调度的方法优化处理器的能耗;(2)利用混合存储器上的任务分配的方法优化存储器的能耗、空间以及延长存储器的寿命;(3)利用循环变换的方法优化存储器的时间与空间性能。现将本文研究的这几个问题以及所做的工作列举如下:1能耗问题已成为嵌入式系统设计中考虑的主要因素。在系统的众多设备中,处理器通常消耗最多能量。在本文中,我们利用任务调度技术来优化处理器所消耗的能量。在该问题中,每个任务具有两个属性:n(n≥1)个活跃时间区间和一个工作量。任务可以在n个活跃时间区间内被处理,要求在所有时间区间内所作的工作量之和达到给定的工作量。任务遵循可抢占式的调度策略。处理器的处理速度可以为任意值,且能够在两个不同速度间进行瞬时切换。在以前人们研究的多区间任务调度问题中,每个任务必须在其中某一个区间内完成给定的工作量。若在该区间结束时未能完成,则之前所作的工作被视为无效,需要在以后的某个区间中重新开始做。本文中,我们研究的问题与之前人们研究的有所不同:任务不必在其中一个时间区间内完成,只要在其所有时间区间内所作的工作量之和达到给定的工作量要求即可视为任务完成。目标是找到一个可行的调度方案以最小化处理器的能耗。我们所作的工作是:提出了一个多项式时间算法,并证明了算法的最优性。2除处理器外,存储器也是嵌入式系统中一个重要的耗能单元。对此,本文提出了优化存储器能耗的方案。我们考虑由DRAM与PRAM组成的混合存储器中的任务分配问题。由于PRAM具有极低的泄漏功率(leakage power),故PRAM与传统存储器DRAM相比,功耗更低。但PRAM的缺点是写操作次数有限且延迟较大。所研究的问题包含以下目标:减小能耗,减少PRAM上的写操作次数以延氏寿命,以及减少PRAM的窄间需求。对此,我们提出了两种解决方法:一种为整形线性规划(Integer Linear Programming),该方法可以得到问题的最优解,但通常比较耗时。另一种方法为多项式时间复杂度的启发式算法。实验结果显示,与可以得到最优解的ILP方法相比,所提出的启发式算法能得到近似最优解,但所需时间可以忽略不计。3由于很多嵌入式系统通常具有实时性要求,且存储器的容量有限,故在嵌入式系统设计中,时间与空间性能是除能耗以外的两个需要考虑的重要因素。在本文中,我们研究了一种特别的嵌入式系统—流处理系统(Stream Processing System),该系统近年来被广泛应用于多媒体与科学计算等领域。其中,流寄存器文件(Stream Register File, SRF)是系统中的关键资源,这是凶为所有数据需要置于SRF中才能被处理。SRF是一种非旁路(non-bypassing)的由软件控制(software-managed)的片上(on-chip)存储器。通常,其容量有限,且与主存之间的带宽较小。因此,将程序由主存载入SRF中执行时,对SRF的空间需求以及数据传输时间成了影响系统性能的两个重要因素。本文利用循环变换(loop transformation)技术埘需要执行的程序进行处理以优化SRF。考虑的日标有两个:减小占用的SRF空间,减小数据传输时间。我们证明了SRF的优化问题是NP难的,并且提出了启发式算法。实验结果表明所提出的启发式算法能有效地提高系统的时间与空间性能。