2016 45届 并行处理国际会议
了解EDA算法的体系结构特征
王欣, 纪晓峰, 陆云萍, 李毅,周伟嘉,张伟华, 赵文云
中国上海复旦大学软件学院
中国上海复旦大学数据科学重点实验室
中国上海复旦大学计算机科学与技术学院
中国上海复旦大学并行处理研究所
{xin wang,xfji11,15110240023,liy,zhouwj13,zhangweihua,wyzhao}@fudan.edu.cn
摘要—目前，不同的芯片产品在不断地被发布。这些产品的上市时间已缩短到接近极致的8到12个月。为了缩短生产周期，硬件架构工程师试图缩短每个设计和制造阶段。因此，如何使在芯片设计和制造的整个生命周期中被广泛使用的电子设计自动化（EDA）工具加速运行已成为他们的主要关注点之一。虽然他们先前已经深入研究了不同的加速技术，如基于IC的，基于FPGA的或基于GPU的加速技术，但就我们所知，硬件架构工程师尚未对这些EDA算法的架构特性分析进行系统研究。这可能会阻碍他们进一步的优化和加速。
本文中，我们首次尝试构建EDA基准套件（简称EDAbench），用于架构设计，并行加速和系统优化。 EDAbench涵盖了代表性的现代EDA算法。 然后，我们从三个方面评估主要的架构特征，包括计算特征，内存层次和系统特征。实验结果表明，现有的硬件与EDA算法的要求之间存在一些重要差距。
- 介绍
根据世界半导体贸易统计公司（WSTS）的最新报告，在过去的二十年中，全球半导体行业的市场收入保持增长。同时，由于移动设备和数据中心的发展，芯片的多样性也显著增加。另一方面，产品上市时间的压力推动半导体制造业减少硬件设计周期。根据之前的研究，硬件设计过程通常需要大约9个月的时间，而上市时间目前已缩短到8到12个月左右。因此，为了跟上日益增长的市场需求，硬件架构师优化电子设计自动化（EDA）工具的性能变得越来越重要，这些工具在整个芯片设计和制造的整个生命周期中发挥着至关重要的作用。
自20世纪80年代初以来，EDA工具已成为半导体生产中所有设计和制造阶段的基本组成部分。随着设计规模和复杂性的增加，对加快设计周期的需求给主流EDA工具带来了巨大压力。根据英特尔的“Tick-Tock”设计模型，现代CPU的典型设计周期通常延长至1-2年，其中一些关键阶段（如验证）可能成为瓶颈。为了解决这个问题，EDA工具有很多优化和加速技术。然而，他们大部分都专注于特定硬件平台上的一些特殊优化，例如定IC，FPGA和GPGPU。据我们所知，对于为这些工作负载设计和实现更高效的架构和系统至关重要的基准测试和架构特征分析方面还没有系统地研究。
在最初的尝试中，我们通过选择主要EDA工具中采用的代表性算法来设计和构建用于架构设计和系统优化的EDA基准测试套件。这些算法涵盖了EDA工作流程的所有阶段和EDA工具的主流算法模式。此外，我们还为用户提供了一些工具来调整参数和输入。这样一来，用户可以灵活地使用不同的参数和输入来评估他们的设计。
此外，我们使用性能计数器来研究EDA算法的系列特性。我们观察到EDA工作负载需求与当前主流处理器架构之间的明显不匹配，这也揭示了为什么这些EDA算法无法在许多通用硬件平台上有效执行。我们从三个层面总结这些工作负载的特点。从计算角度来看，这些算法具有以下特点：（1）复杂的分支行为；（2）低指令级并行性（ILP）和存储级并行性（MLP）； （3）浮点运算强度高，可用定点代替；（4）计算强度高。从内存或缓存的角度来看，这些算法具有以下特点：（1）适度大小的L2缓存和LLC可以高效工作；（2）记忆强度不如计算强度高；（3）指令工作集可以很好地适应当前的现代处理器体系结构。从系统角度来看，
大多数EDA工作负载可以很好地适应当前的带宽配置，并有很多空闲的地方。
在实验过程中，我们观察到一些值得注意的EDA算法的架构特征。在分析的基础上，我们也提供了一些见解，并为未来的优化，加速和架构设计提出了建议。
总之，本文分为以下模块：
bull;设计和制作用于架构设计和性能评估的EDA基准测试套件，包括具有代表性的EDA算法和自动化工具；
bull;分析EDA基准的架构特征；
bull;针对EDA系统未来优化，加速和架构设计的一些见解和建议。
本文的其余部分安排如下：第二部分讨论动机。 第三部分介绍了相关的工作，包括之前关于EDA优化和主要基准测试套件的工作。 第四部分概述了我们的基准测试套件以及所选工作负载的详细信息。 第五部分给出了实验的方法，包括实验环境，指标和工具。
Ⅱ. 动机
EDA工具在芯片设计和制造的整个周期中发挥着至关重要的作用。 如前面的研究所示，EDA包含一系列计算密集型阶段，如逻辑综合，布局规划和布局。目前，处理器设计正变得越来越复杂，规模也在不断增加。 此外，芯片设计的产品发布时间紧张，需缩短至12个月以内，上市时间压力日益增长。 所有这些因素都给EDA工具的处理速度带来了相当大的压力。
为了解决这些问题，研究人员已经在并行硬件平台（如FPGA和GPGPU）中利用计算资源进行了许多关于EDA工具加速的研究。 尽管已经实现了一些性能改进，但是针对一种或两种算法设计的这些优化技术对于其他EDA算法是否同样有效还不清楚。 此外，还不清楚可以采用哪些优化措施来进一步提高性能，哪些硬件功能对他们更有效。背后的主要原因是缺乏基准套件和这些EDA算法的系统特性分析。
考虑到EDA算法面临的这些挑战，我们打算加深对EDA算法系统和体系结构表征的理解，以便为进一步的优化和体系结构设计提供一些见解。为了实现这样的目标有必要设计和实现EDA算法的基准测试套件。此外，分析它们的特征也是必不可少的，以便为将来的相关研究提供资料，例如优化或加速。 框架如图1所示：
图1：一般EDA优化过程的方法。
为了实现上述所有目标，选择构成基准套件的工作负载应满足以下先决条件:
bull;普遍性：基准测试套件中使用的工作负载应反映EDA工具的最新技术。因此，算法应该在主要的EDA平台中被广泛采用；
bull;代表性：基准旨在为不同的评估需求提供一个通用的解决方案，因此它要求工作负载应该足够主流，并覆盖整个EDA工作流程的每个阶段；
bull;灵活的基础架构：为了满足不同的需求，设计的基准测试套件中的一些配置应该易于调整，例如输入数据的大小和运行时参数。
Ⅲ. 相关工作
为了跟上新兴市场的要求，EDA工具的处理速度已成为EDA优化的主要关注点。 在本节中，首先讨论以前关于EDA算法加速技术的研究。然后，讨论几个现有的基准套件。
- 以前的EDA优化
目前，EDA算法的加速主要基于并行硬件平台，包括定制IC，FPGA和GPGPU。所有这些工作都在EDA算法上取得了显着的性能改进，而其中大部分工作主要集中在改进一个特殊算法在一个特殊硬件平台上的性能。 目前尚不清楚这些优化是否对其他EDA算法有效，可以采用哪些优化来进一步提高性能，以及哪些硬件功能对其更有效。这种情况可能会阻碍这些算法的进一步优化和并行加速。这背后的主要原因是缺乏相关的基准套件和这些EDA算法的系统特性分析，而对基准套件和这些EDA算法的系统特性分析则是本文的目的。
B.主导基准套件
作为基准测试套件设计的参考，我们对主要基准套件进行了调查，并选择一些候选对象进行比较：1）SPEC设计了几个基准测试套件，例如SPEC CPU和SPEC JVM，以满足不同的评估方案；2）Splash2和PARSEC是并行系统评估中两种最流行的并行基准；3）Parboil基准测试是另一个平行基准测试套件，它主要关注类似GPGPU的体系结构。
我们主要关注可以在多个平台上采用的通用基准套件。 基于空间限制，暂时不考虑为诸如多媒体，网络和云计算等特定领域设计的基准。 在我们的评估部分，我们还将采用SPECint，SPECfp和PARSEC等通用基准套件进行比较。
在上述主要的传统基准测试套件中，EDA算法并未引起足够的重视。 在这些套件中，可以找到一些与EDA相关的算法，例如：
SPEC CPU 2006采用了175.vpr（使用模拟退火的FPGA布局），181.mcf（使用Simplex算法的ILP求解器）和300.twolf（标准单元布局和布线封装）作为工作负载。 同样，PARSEC基准套件还包括canneal（使用模拟退火的芯片布线）。因为这些基准主要集中在通用平台的设计和评估上，所以只选择很少的EDA算法。因此，对这些算法的分析既不能代表EDA算法的行为，也不能为EDA算法的进一步优化和加速提供帮助。
Ⅳ.基准套件概述
主流EDA算法主要在芯片设计和制造的四个主要步骤中采用：设计，仿真，分析和验证，其中每一个都包含各种算法。因此所选择的算法应该涵盖上述所有阶段。为保证代表性和普遍性，我们在过去三年中对DAC，ICCAD和DATE等计算机辅助设计和设计自动化顶级会议进行了调查。如果一个算法被引用超过某个阈值，它就被认为是最先进的，并在这个基准套件中被选中。目前，我们在此工作中将阈值设置为50，因为所选算法的最低引用数量与未选定算法的最高引用数量之间存在明显差距。
因此，基准套件中选择了九种算法，如表1所示。关于这些算法的详细信息如下所示：
表1：选定工作负载的类别
|
模式 |
算法 |
主导应用阶段 |
|
分支定界 |
分支定界（B amp; B） |
设计/综合 |
|
SAT（CNF-布尔可满足性） |
验证 |
|
|
二元决策图（BDD） |
模拟 |
|
|
图形算法 |
图形分区 |
设计/综合 |
|
斯坦纳树 |
设计/综合 |
|
|
线性代数 |
共轭梯度法（CGM） |
验证 |
|
线性规划（LP） |
设计/综合 |
|
|
随机算法 |
模拟退火（SA） |
设计/综合 |
|
蒙特卡洛（MC方法） |
模拟 |
|
bull;线性规划（LP，或线性优化）提供了一种通用的数学方法，用于在给定的数学模型中获得以线性关系表示的特定需求列表的最佳结果（如最大利润或最低成本）。在EDA工作流程中，线性规划，特别是与矩阵相关的操作经常在合成或平面规划的过程中采用。
bull;SAT（CNF-布尔可满足性）旨在确定是否存在满足给定布尔公式的解释。 也就是说，它确定了给定的布尔公式的变量是否可以用公式计算为TRUE的方式来分配。 基于SAT的模拟验证是处理复杂混合信号（AMS）设计的流行方法。
bull;蒙特卡洛方法（MC方法）是指依赖于重新随机抽样获得数值结果的一大类计算算法。通过多次运行模拟，以启发式的方式计算相同的概率。蒙特卡洛技术通常在晶体管级仿真过程中用于分析设计的统计行为。
bull;共轭梯度法（CGM）是特定线性方程组的数值解的算法，即矩阵是对称和正定的。共轭梯度法是一种离散方法，广泛用于大规模电网分析中的泊松求解器。
bull;斯坦纳树表面上类似于最小生成树（MST）问题。它们之间的区别在于，在斯坦纳树问题中，可以将额外的中间顶点（斯坦纳点）和边添加到图中以减少生成树的长度。 直线斯坦纳树对于现代VLSI设计中的最佳路由解决方案非常实用。
bull;二进制决策图（BDD）或分支程序，是用于表示布尔函数的数据结构。在更抽象的层面上，可以将BDD视为集合或关系的压缩表示。 加权二元决策图被广泛应用于约束随机模拟中，正在成为功能验证的主流方法。
bull;图形分区问题定义为以G =（V，E）的形式表示的数据，其中包含V个顶点和E个边，从而可以将G划分为具有特定属性的较小组件。 在设计一些多处理器片上系统（MPSoC）器件的存储器架构时，经常使用与图形分区相关的算法。
bull;模拟退火（SA）是一个全局优化问题的通用概率元启发式，用于在大型搜索空间中定位一个给定函数的全局最优值的近似值。 自从EDA软件在20世纪90年代开始在半导体制造业中占据重要地位以来，模拟退火技术开始被用于数字贴装技术的研究。
bull;分支定界（B＆B）被广泛用于搜索各种优化问题的最优解，其中包括所有候选解的系统列举，其中通过使用优化数量的估计界丢弃无用结果的大量子集。分支定界算法在实现微机电系统后硅调谐的高效启发式算法中有着广泛的应用。
在以前的研究中，EDA算法也可以分为几种设计模式。为了验证选定算法
全文共8349字，剩余内容已隐藏，支付完成后下载完整资料
2016 45th International Conference on Parallel Processing
Understanding the Architectural Characteristics of
EDA Algorithms
Xin Wang dagger;sect;, Xiaofeng Ji dagger;sect;, Yunping Ludagger;Dagger;sect;, Yi Li dagger;sect;, Weijia ZhouDagger;, Weihua Zhang dagger;sect;, Wenyun Zhaodagger;Dagger;sect;
Software School, Fudan University, Shanghai, China
-
Shanghai Key Laboratory of Data Science, Fudan University, Shanghai, China
-
School of Computer Science, Fudan University, Shanghai, China
- Parallel Processing Institute, Fudan University, Shanghai, China
-
School of Computer Science, Fudan University, Shanghai, China
{xin wang,xfji11,15110240023,liy,zhouwj13,zhangweihua,wyzhao}@fudan.edu.cn
Abstract—Currently, the release of different chip products has come to a burst. Time-to-market period of these products has been shortened to an extreme, nearly 8 to 12 months. To reduce production period, hardware architects try to shorten every design and manufacture stage. Therefore, it has become one of the major concerns for them that how to accelerate electronic design automation (EDA) tools, which have been widely used throughout the lifetime of chip design and manufacture. While many prior efforts have done in-depth works on different acceleration techniques, such as IC-based, FPGA-based, or GPU-based, to our best knowledge, there has been no systematic study towards the architectural characteristics analysis for these EDA algorithms. This may impede the further optimizations and acceleration for them.
In this paper, we make the first attempt to construct an EDA benchmark suite (EDAbench for short) for architectural design, parallel acceleration, and system optimization. EDAbench covers representative modern EDA algorithms. We then evalu-ate predominant architectural characteristics from three aspects including computation characteristics, memory hierarchy, and systematic characteristics. Experimental results reveal that there are some vital gaps between existing hardware and the require-ments of EDA algorithms.
I. INTRODUCTION
According to the latest report from World Semiconductor Trade Statistics (WSTS) [1], worldwide market billings of semiconductor industry keeps growing in the last two decades. Meanwhile, the diversity of chips also increases significantly due to the development of mobile devices and data centers. On the other hand, the increasing time-to-market pressure pushes the semiconductor manufacture industry to accelerate the cycle of hardware design. According to the previous research, the hardware design process usually takes around 9 months while the time-to-market has currently been shortened to around 8 to 12 months [2]. Therefore, to keep pace with the increasing market needs, it has become more and more important for hardware architects to optimize the performance of electronic design automation (EDA) tools which play a vital role through-out the lifetime of chip design and manufacture.
Since the early 1980s, EDA tools have become an es-sential part through all design and manufacture stages in semiconductor production. With the increase of design scale and complexity, the need for accelerating design cycle puts great pressure on the predominant EDA tools. According to Intel ”Tick-Tock” design model [3], the typical design cycle of a modern CPU often stretches to 1-2 years within which
some key stages, such as verification, could be the bottleneck. To solve this problem, there have been a lot of optimizing and accelerating techniques for EDA tools. However, most of them focus on some special optimization on specific hardware platforms, such as custom IC, FPGA, and GPGPU. To our best knowledge, there have been no systematic efforts on benchmarking and architectural characteristics analysis, which are critical to design and implement more efficient architectures and systems for these workloads.
As an initial attempt, we design and construct an EDA benchmark suite for architectural design and systematic opti-mizations through selecting representative algorithms adopted in predominant EDA tools. The algorithms cover all the stages in EDA workflow and mainstream algorithm patterns of EDA tools [4]. Moreover, we also provide some tools for users to adjust the parameters and inputs. Therefore, users can flexibly evaluate their designs by using different parameters and inputs.
Furthermore, we use performance counters to study a se-ries of architectural characteristics of EDA algorithms. We observe obvious mismatch between EDA workloads need and current predominant processor architecture, which also reveals why these EDA algorithms cannot efficiently execute on many general-purpose hardware platforms. We conclude the characteristics of these workloads in three levels. From computation perspective, these algorithms have (1) Complex branch behavior; (2) Low instruction-level parallelism (ILP) and memory-level parallelism (MLP); (3) High intensity on floating point operations, which could be substituted by fixed point ones; (4) High computational intensity. From memory or cache perspective, these algorithms have the following characteristics: (1) Modestly sized L2 cache and LLC could work efficiently; (2) Memory intensity is not as high as computational intensity; (3) Instruction working set could fit well in current modern processor architecture. From system perspective, most EDA workloads could fit well in the current bandwidth configuration with much spare place.
We have observed some noteworthy architectural charac-teristics of EDA algorithms during the experiment. Based on the analysis, we also give out some insights and propose sug-gestions for future optimization, acceleration, and architecture design.
In summary, this paper makes the following contribu-tions:
-
Designing and implem
全文共28866字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[14485]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
