动态电压调度(Dynamic Voltage Scaling,DVS)是一种有效的分布式嵌入式系统的系统级低功耗技术.这种技术通过降低系统中的处理部件的频率和电压,使得处理部件的功率显著下降,同时由于频率的下降造成执行时间的上升相对较小,这样,处理部件的功耗就得到降低. 这项技术吸引了很多研究人员的研究兴趣,提出了动态电压调度算法.有些算法得到了非常理想的结果,然而,有些算法,例如EE～GLSA[24],在连续电压可调的假设下,所得到的结果的有效性很大程度上依赖于电压模式数量,电压模式越多,功耗降低也越多;另一些算法,虽然得到很好的结果,但是时间复杂度过大. 本文在分析低功耗设计技术和典型DVS算法的基础上,在电压模式为离散可调的基础上,提出了一种基于蚁群算法的电压和任务调度算法ACO-VTS(Ant Colony Optimization)及其线性时间复杂度的近似算法.ACO-VTS算法首先按照一种基于优先级的任务调度算法调度所有将要在系统中运行的任务,得到尽可能多的空闲时间,然后定义了一种非常有效的"蚁酸"函数(电压模式选择概率函数),按照蚁群算法的进行搜索.由于蚁群算法非常适合于分布式实现,我们采用用带有MPI库的C++语言并行实现,并在曙光刀片机上进行了模拟.实验结果表明,这种算法可以达到线性时间复杂度,得到比以往算法更好的结果,有的算法结果比以前升高了30﹪,同时结果的有效性不依赖于电压模式的数量.在近似算法中,我们定义了功耗密度的概念作为启发式函数,并以此来进行局部搜索,这种算法以无回溯的方式达到了线性时间复杂度,同时实验结果和ACO-VTS的一样好.最终,我们将这种近似算法加入到ACO-VTS的每一个"蚂蚁"的搜索过程中,这种带有局部搜索的蚁群算法的电压调度算法以更快的收敛速度得到了更好的结果. 同时,本文还提出了基于负载的在线动态电压调度算法,并在Linux 2.6.17内核上实现,这种在线的算法对系统负载的细微变化及时调整处理器的工作电压和频率,达到最优的功耗和性能.基于负载的动态电压调度算法的实现在三星s3c2410处理器上运行良好.