AnalyticalClusteringScorewithApplicationtoPost-PlacementMulti-BitFlip-FlopMerging

198 浏览量 2021-02-10 04:34:38 上传评论收藏 1.65MB PDF 举报

本文探讨了一种分析聚类分数（Analytical Clustering Score）的应用，这项技术特别应用于后放置多比特触发器（Multi-Bit Flip-Flop, MBFF）合并。聚类分析是电路设计中的一种重要技术，它通常通过离散优化来实现，目的是为了减少电路的规模或形成特定设计的聚类。作者对特定于时钟功率减少的MBFF设计技术进行了探讨。目前，所有相关的工作都依赖于离散聚类优化，例如，INTEGRA是唯一已知的具有次二次时间复杂度的后放置MBFF聚类优化器。然而，INTEGRA在某些实际设计中严重退化了连线长度，这可能会抵消MBFF聚类带来的好处。本研究通过在非线性规划中启用分析聚类分数的公式化，成功整合了连线长度目标。所提出的方法具有次二次时间复杂度，并且可以将时钟功率减少约20%，在其他技术中处于领先地位。除此之外，连线长度也减少了大约25%。另外，所提出的方法有望集成到一个原地MBFF聚类求解器中，并应用于其他需要在目标函数中制定聚类分数的问题。在引言部分中，作者介绍了电路聚类技术是电子设计自动化中的一个重要阶段，并将其分为两大类：一类用于电路规模的减少，另一类则是为了特定设计的聚类。电路聚类技术在集成电路设计中起着至关重要的作用，特别是在布局与布线设计辅助方面。本文所提出的分析聚类分数方法不仅降低了时钟功率，而且优化了连线长度，这对集成电路设计的效率和性能至关重要。在深入研究之前，需要对一些关键概念进行定义和解释。例如，多比特触发器（MBFF）是一种电路设计技术，它能够通过减少时钟信号的数量来降低芯片的功耗。在现代集成电路设计中，时钟功率通常占据整体功耗的一个相当大的比例，因此，采用MBFF技术有助于提高芯片的能效。然而，这项技术的有效实施需要复杂的电路聚类优化算法来确保电路的性能不被牺牲。在讨论中，作者提到了INTEGRA这一特定的聚类优化器，并指出它在减少连线长度方面的不足。连线长度对集成电路的设计性能有着显著的影响，特别是在高密度、高性能的集成电路设计中。过长的连线不仅增加了时钟周期的延迟，而且可能导致更多的功耗，这在许多应用场景中是不可接受的。因此，设计一个既能减少时钟功率又能优化连线长度的聚类算法是电路设计领域的一个重要挑战。本文的关键贡献在于提出了一种新型的分析聚类分数公式化方法，这种技术可以无缝地集成连线长度目标，并在保持次二次时间复杂度的同时，显著提高了时钟功率和连线长度的优化性能。这一点对于实际电路设计有着直接的积极影响，因为它不仅降低了能耗，还提高了电路的性能和可靠性。作者指出，该方法有望在原地MBFF聚类求解器中得到集成，并且可以应用于其他需要在目标函数中定义聚类分数的优化问题。这意味着所提出的方法具有广泛的应用前景，并且可能对集成电路设计的其他方面产生积极的推动作用。随着集成电路设计复杂性的增加，能够提供有效聚类优化的技术将变得越来越重要。总结来说，本研究提出了一种创新的方法，用于解决电路设计中的关键问题，即在保持电路性能的同时降低功耗和连线长度。这项工作不仅在理论上具有创新性，而且在实际应用中具有重要意义，有潜力显著改善集成电路设计的质量和效率。

资源推荐

资源详情

资源评论

Analytical Clustering Score with Application to

Post-Placement Multi-Bit Flip-Flop Merging

Chang Xu

, Peixin Li

, Guojie Luo

1,2

, Yiyu Shi

, and Iris Hui-Ru Jiang

Center for Energy-Efﬁcient Computing and Applications, School of EECS,

Peking University, Beijing, 100871, China

PKU-UCLA Joint Research Institute in Science and Engineering

Dept. of ECE, Missouri University of Science and Technology, Rolla, MO 65409, USA

Dept. of EE and Inst. of Electronics, National Chiao Tung University, Hsinchu 30010, Taiwan

{changxu, gluo}@pku.edu.cn, pageli328@gmail.com

yshi@mst.edu, huiru.jiang@gmail.com

ABSTRACT

Circuit clustering is usually done through discrete optimiza-

tions, with the purpose of circuit size reduction or design-

speciﬁc cluster formation. Speciﬁcally, we are interested in

the multi-bit ﬂip-ﬂop (MBFF) design technique for clock

power reduction, where all previous works rely on discrete

clustering optimizations. For example, INTEGRA was the

only existing post-placement MBFF clustering optimizer with

a sub-quadratic time complexity. However, it degrades the

wirelength severely, especially for realistic designs, which

may cancel out the beneﬁts of MBFF clustering. In this

paper we enable the formulation of an analytical clustering

score in nonlinear programming, where the wirelength ob-

jective can be seamlessly integrated. It has sub-quadratic

time complexity, reduces the clock power by about 20% as

the state-of-the-art techniques, and further reduces the wire-

length by about 25%. In addition, the proposed method is

promising to be integrated in an in-placement MBFF clus-

tering solver and be applied in other problems which require

formulating the clustering score in the objective function.

Categories and Subject Descriptors

B.7 [Integrated circuits]: design aids placement and rout-

ing

Keywords

Multi-bit ﬂip-ﬂops, placement, clock power, timing

1. INTRODUCTION

Circuit clustering technique is a useful stage in electronic

design automation. There are two categories of clustering

problems: one is for circuit size reduction, where a short

survey can be found in [20]; the other is for design-speciﬁc

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for proﬁt or commercial advantage and that copies bear this notice and the full cita-

tion on the ﬁrst page. Copyrights for components of this work owned by others than

ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-

publish, to post on servers or to redistribute to lists, requires prior speciﬁc permission

and/or a fee. Request permissions from permissions@acm.org.

ISPD’15, March 29–April 1, 2015, Monterey, CA, USA.

2015 ACM 978-1-4503-3399-3/15/03 ...$15.00.

http://dx.doi.org/10.1145/2717764.2717767.

Figure 1: Clock tree synthesis for (a) conventional

ﬂow (b) MBFF ﬂow

Table 1: The power and area of our MBFF library

Bit number Normalized Normalized

power per bit area per bit

1 1.00 1.00

2 0.86 0.96

4 0.78 0.71

cluster formation, such as voltage island grouping [19] and

In this paper we are interested in the multi-bit ﬂip-ﬂop

(MBFF) clustering problem, which is a promising technique

for clock power reduction, due to the power savings on clock

nets and ﬂip-ﬂops (FFs) themselves. As shown in Figure

1, the basic idea of MBFF technique is to reduce the load

capacitance on the clock network, including the reduction

of metal wires in the last-level of the clock tree, as well as

the reduction of clock pins. In addition, the normalized per-

bit power and area of a MBFF are less than a single-bit FF.

Speciﬁcally, for the MBFF library we used as shown in Table

1, 4-bit MBFF is the most power-eﬃcient and area-eﬃcient.

Existing works explore MBFF clustering in three design

stages: pre-placement stage [1][10], in-placement stage [17]

[7], and post-placement stage. Because of the adequate

physical information, post-placement MBFF clustering has

attracted a lot of attentions, such as [21][11][18][9]. Among

all these works, INTEGRA[9] delivers the best performance

in both power reduction and runtime consumption and is the

only one with sub-quadratic complexity. However, almost all

previous works pay little attention to the signal wirelength,

either regarding it as secondary objective [21][11][18] or even

ignoring it at all [9]. We demonstrate latter that for a se-

ries of realistic benchmarks, INTEGRA’s clustering degen-

erates into a random clustering of MBFFs and induces huge

degradation of signal wirelength, which might cancel out the

power beneﬁt of MBFFs.

In this paper we propose an analytical model for the clus-

tering score. The basic idea is to ﬁrst propose an exact for-

mulation of the number of clusters based on the Dirac delta

function, and smooth it using the Gaussian function to make

it applicable in a nonlinear programming (NLP) framework

with another objective in wirelength. With a well-designed

NLP solver, the acceleration techniques such as customized

fast Gauss transformation, and a further discrete reﬁnement,

our clustering ﬂow delivers high-quality MBFF clustering re-

sults with short wirelength in sub-quadratic time. Taken IN-

TEGRA as baseline, our method shows a comparable power

reduction, reducing clock power by about 20%. Further-

more, our method optimizes signal wirelength by about 25%.

What’s more, the proposed method is promising to be in-

tegrated in an in-placement MBFF clustering solver, and

be applied in other problems which require formulating the

clustering score in the objective function.

The rest of this paper is organized as follows. Section 2

reviews the eﬀectiveness and limitations of previous work.

Section 3 introduces our optimization ﬂow, including ana-

lytical clustering model and discrete reﬁnement. Section 4

elaborates the details of NLP solver and the acceleration

technique. Section 5 evaluates our method, and shows ex-

perimental data and comparisons. Finally, Section 6 con-

cludes this work.

2. PRELIMINARY AND MOTIVATION

This section will focus on two concepts, the timing violation-

free distance (TVFD) and the average distance between neigh-

boring ﬂip-ﬂops (AFFD). The concept of TVFD will be de-

scribed in Section 2.1, and the concept of AFFD and our

motivations will be discussed in Section 2.2.

2.1 Post-placement MBFF Problem Formula-

tion and Previous Solutions

Given the following inputs, the post-placement MBFF

clustering problem will replace a few single-bit FFs with

MBFF such that the power is minimized and the timing

constraint and placement density constraint are satisﬁed.

• The number of N placed ﬂip-ﬂops (FFs), where each

with coordinate (x

, y

) can either be single-bit or

multi-bit.

• The upstream pin PI

and downstream pin PO

, and corresponding timing slacks T

(PI

, FF

) and

(PO

, FF

) between the pins and FF on the up-

stream and downstream timing paths, respectively.

• The MBFF library with information of power and area.

• The locations of placement blockages.

Timing constraint is proposed to prevent MBFF cluster-

ing from violating cycle delay. The basic idea is shown in

Figure 2. With timing analysis, we could obtain timing slack

between input (output) pins and FF. By transforming the

timing slack into equivalent metal wirelength using Elmore

Figure 2: Concept of timing-violation-free distance

(TVFD) and timing-violation-free region (TVFR)

delay model [4], we can ﬁnd the timing-violation-free dis-

tance (TVFD) between FF and input (output) pins. Taken

the input and output TVFDs into account, each FF can

ﬁnd a feasible region for movement without violating timing,

which we label as timing-violation-free region (TVFR) in

Figure 2. Consequently, clustering a few single-bit FFs with

overlapped TVFRs can optimize power and area without vi-

olating timing constraint. Speciﬁcally, using the library in

Table 1, the basic objective of MBFF clustering problem

should merge FFs with overlapped TVFRs into 4-bit groups

as many as possible.

Previous works certify the timing constraint with well-

designed structures: intersection graph [21][11][18] or in-

terval graph [9] and search the MBFF candidates on these

graphs.

The MBFF clustering based on intersection graph has the

following defects: 1) searching maximum clique is computa-

tional expensive with known best performance of O(N

). 2)

The window-based optimization technique for problem size

reduction limits the clustering ratio of MBFF due to the

diﬃculty of manipulating the boundaries.

Unlike window-based technique, INTEGRA considers all

FFs simultaneously, with a well designed structure: interval

graph. Searching on the interval graph is more eﬃcient, with

sub-quadratic complexity. Moreover, the optimization with

global information delivers better clustering ratio than the

optimization with local information only. Thus, INTEGRA

outperforms the previous work in terms of power reduction

and runtime complexity.

However, the eﬃcient runtime of INTEGRA partially ben-

eﬁts from the simple strategy of choosing MBFF candidates

without measuring the impact to signal wirelength. Taking

an extreme case as example, where the intervals of feasible

region for each FF is as large as the placement region, INTE-

GRA’s solution degenerates to a random solution. Although

the wirelength degradation on widely used benchmarks C1-

C6 [11] is acceptable (around 3%), we analyze in the follow-

ing subsection that for a series of realistic designs, wirelength

degradation is quite huge. Such observation motivates us to

propose a new solution with great power reduction, better

signal wirelength and eﬃcient time complexity.

2.2 Previous Solutions are Inappropriate for

Realistic Designs

We demonstrate in this part that 1) the widely used bench-

marks C1-C6 [11] can only represent a single kind of circuit;

2) realistic designs from IWLS[2] are quite diﬀerent from

C1-C6 in terms of TVFR. Speciﬁcally, for the realistic de-

剩余7页未读，继续阅读

评论收藏

内容反馈

weixin_38548704

粉丝: 3
资源: 931

Analytical Clustering Score with Application to Post-Placement M...

最新资源

Analytical Clustering Score with Application to Post-Placement M...

Analytical-design-of-robust-control.rar_robust control_time dela

Analytical study on holographic superconductors for Born-Infeld electrodynamics in Gauss-Bonnet black hole with backreactions

A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort (sigmod14I)-计算机科学

An.Introduction.to.Machine.Learning.with.Application.in.R

New Analytical Solution of a Generalized Negative Variable-coefficient eKdV Equation in Internal Wave

Mastering Machine Learning with scikit-learn -2017.7.24

Python: End-to-end Data Analysis.azw3电子书下载

Biostatistics with R_ An Introduction to Statistics Through Biological Data

Analytical Method for Designing Grating Compensated Dispersion-Managed Soliton Systems

A two-dimensional fully analytical model with polarization effect for off-state channel potential and electric field distributions of GaN-based field-plated high electron mobility transistor

Analytical Methods in Anisotropic Elasticity-with Symbolic Computational Tool

Mastering Machine Learning with scikit-learn [2017,第二版]

Semi-analytical model for hollow-core anti-resonant fibers.

Analytical dynamics 1999-Haim Baruh

Analytical Network and System Administration: Managing Human-Computer Systems

Analytical-computation-of-nodal-voltage-sensitivity-coefficients

An Analytical Approach to Calculating

Fundamentals of Vibrations - L.Meirovitch

RF and Digital Signal Processing for Software-Defined Radio

Pro Hadoop Data Analytics(Apress,2016)

Pro Hadoop Data Analytics

Handbook of Research on Soft Computing and Nature-Inspired Algorithms

Analytical self-similar solutions of the Ginzburg-Landau equation with three-order dispersion effect

Concurrency in Main-Memory Database Systems

最新资源