VLSI高层综合设计低功耗调度算法的研究与实现

摘要

目前，随着集成电路规模的不断增大和工作频率的不断提高，功耗已经成为除面积和性能之外的主要设计目标。超大规模集成电路低功耗设计可以在不同的设计层次进行考虑，自下而上分可以分为：物理层、逻辑层、结构层、算法（行为）层和系统层。每个层次可以达到低功耗设计效果也完全不同，抽象层次越高表明能够越早进行低功耗设计，因此层次越高低功耗设计的效果就越明显。
　　本文主要研究行为级的低功耗调度技术，是在多约束条件下，把工作在不同电压下的操作分成具体的时间段进行执行的过程。文中分析了三类基于不同约束条件下的多电压调度算法：基于资源约束的调度算法、基于时间约束的调度算法和基于时间和资源约束的调度算法。基于资源约束的调度算法尽量在最大化地利用低能耗资源和减少运行时间之间达到平衡，文中采用基于list-based的调度算法。基于时间约束的调度算法通过尽可能多地分配低电压操作来降低功耗，文中提出了三种不同的低功耗调度算法，它们分别具有较低的复杂性、较好的优化效果和较强的整体优化能力。基于时间和资源约束的调度算法在满足时间和资源约束的条件下，尽量在最大化地分配有限的低能耗资源和减少运行时间之间达到平衡。本文中提出了基于Gain大小搜索的时间和资源约束的调度算法，该算法具有较好的优化效果和较低的时间复杂度。由于多电压调度是NP-hard问题，本文还采用了一种基于模拟退火搜索的时间和资源约束的调度算法，该算法是一种启发式的搜索算法，通过与基于Gain大小搜索的调度算法的对比，数据表明两算法优化效果接近，但此算法具有较低的时间复杂性。
　　本文采用或提出的算法中，基于资源约束的调度算法时间复杂度为(log)Onn()On，基于时间约束的调度算法中，第一个算法的时间复杂度为，后两个为()On2，而基于时间和资源约束的调度算法中，基于gain搜索的调度算法时间复杂度为(log)Onn3，基于模拟退火搜索的调度算法时间复杂度为(log)Onn2。

目录

VLSI高层综合设计低功耗调度算法的研究与实现

THE STUDY AND IMPLEMENTATION OF SCHEDULING ALGORITHM IN LOW POWER VLSI DESIGNS

摘要

Abstract

第1章 绪论

1.1 课题概述

1.1.1 课题来源

1.1.2 课题背景

1.2 研究现状分析

1.3 主要研究内容

1.4 论文结构

第2章 预备知识

2.1 概念定义

2.2 CMOS电路功耗的来源

2.3 本章小结

第3章 基于资源约束的调度算法

3.1 多电压调度算法简介

3.2 基于list-based调度算法

3.2.1 节点优先级定义

3.2.2 算法描述

3.2.3 实例分析

3.2.4 时间复杂度分析

3.2.5 实验数据

3.3 本章小结

第4章 基于时间约束的调度算法

4.1 基于mobility和delay比较搜索的调度算法

4.1.1 操作mobility和delay的关系

4.1.2 算法描述

4.1.3 实例分析

4.1.4 时间复杂度分析

4.1.5 实验数据

4.2 基于E-D大小比较搜索的调度算法

4.2.1 算法提出的背景

4.2.2 算法描述

4.2.3 时间复杂度分析

4.2.4 实验数据

4.2.5 算法比较

4.3 基于Group比较搜索的调度算法

4.3.1 算法提出的背景

4.3.2 算法描述

4.3.3 实例分析

4.3.4 时间复杂度分析

4.3.5 实验数据

4.4 本章小结

第5章 基于时间和资源约束的调度算法

5.1 基于Gain大小搜索的调度算法

5.1.1 基于Gain搜索的特点

5.1.2 算法描述

5.1.3 时间复杂度分析

5.1.4 实验数据

5.1.5 算法比较

5.2 基于模拟退火搜索的调度算法

5.2.1 模拟退火简介

5.2.2 接受概率定义

5.2.3 算法描述

5.2.4 时间复杂度分析

5.2.5 实验数据

5.3 两种算法比较

5.4 本章小结

结论

参考文献

附录1 基于list的调度算法流程图

附录2 基于模拟退火搜索的调度算法流程图

攻读学位期间发表的学术论文

哈尔滨工业大学硕士学位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

哈尔滨工业大学硕士学位涉密论文管理

致谢

个人简历