Datapath電路的布局概述

郝燕芳++錢旭++周強(qiáng)

摘 要 集成電路在飛速發(fā)展，相關(guān)的設(shè)計能力卻遠(yuǎn)遠(yuǎn)跟不上集成電路發(fā)展的速度，使得現(xiàn)有的設(shè)計模式也不再適用。Datapath在電路當(dāng)中所占比例越來越高，傳統(tǒng)的設(shè)計模式因沒有考慮到datapath電路本身的特殊性使整個集成電路的性能受到影響，因此，datapath電路的設(shè)計變得尤為重要，而布局又是電路設(shè)計過程中至關(guān)重要的一部分，本文介紹了datapath的設(shè)計現(xiàn)狀、datapath電路的結(jié)構(gòu)特點(diǎn)和布局要求及其布局的基本方法。

【關(guān)鍵詞】集成電路 datapath布局

從20世紀(jì)50年代第一個晶體管問世之后，集成電路制造工藝按照“摩爾定律”飛速發(fā)展，到2012年，中國的集成電路產(chǎn)品產(chǎn)量位居世界第一，占全球出貨量的比重達(dá)到90.6%。隨著集成度的提高，芯片內(nèi)部晶體管數(shù)目越來越多，傳統(tǒng)的手工設(shè)計和小規(guī)模的設(shè)計模式已經(jīng)無法適應(yīng)集成電路越來越高的復(fù)雜性。因此，大力發(fā)展集成電路產(chǎn)業(yè)，極力推動我國信息產(chǎn)業(yè)的發(fā)展，將會極大地促進(jìn)我國的國民經(jīng)濟(jì)和人民的生活水平。然而，與飛速增長的集成電路相比，相關(guān)的集成電路設(shè)計能力卻遠(yuǎn)遠(yuǎn)跟不上時代的腳步，電路的復(fù)雜性以每年58%的速度在增長，相應(yīng)的設(shè)計能力每年的長幅只有21%。Datapath模塊在電路中出現(xiàn)的頻率越來越高，有資料顯示，在現(xiàn)代微處理器中，Datapath模塊的面積已經(jīng)達(dá)到總面積的30%～60%，Datapath已經(jīng)成為現(xiàn)代數(shù)字集成電路的非常重要的組成部分。因此，Datapath單元布局的問題也引起人們的極大重視。如果這一類電路能夠被很好的布局布線，那么電路的集成度和性能將會有很大提高，同時時延、布局面積和擁擠度等都會有所改善。

1 國內(nèi)外datapath布局的基本情況

傳統(tǒng)的布局布線方法只是基于時延、布局面積和擁擠度等作為約束條件進(jìn)行優(yōu)化，數(shù)據(jù)通路本身的特殊性在布局布線當(dāng)中并沒有得到充分的考慮，因此，這種高性能規(guī)則化的數(shù)據(jù)通路電路在布局布線當(dāng)中沒有達(dá)到良好的效果?？偨Y(jié)國內(nèi)外現(xiàn)有的設(shè)計流程和算法，大致可以分為兩種類型，一類是綜合工具，一類是提取工具。

Terry Tao Ye提出的抽象物理模型算法屬于綜合工具：該算法對電路綜合前的邏輯設(shè)計信息進(jìn)行整理，對其中的功能塊進(jìn)行建模，對每一種運(yùn)算單元建立相應(yīng)的標(biāo)準(zhǔn)單元組，并抽象成具有不同I/O數(shù)量和類型的矩形，然后在布局前預(yù)處理網(wǎng)表，采用匹配的方法決定標(biāo)準(zhǔn)單元的歸屬，并把這些單元在布圖區(qū)域里進(jìn)行映射從而完成布局。A.Chowdhary提出的一個自動模板匹配法也屬于綜合工具，該算法同樣是根據(jù)電路邏輯設(shè)計的結(jié)果自動生成一些模板，然后對網(wǎng)表中的單元進(jìn)行匹配，不同的是，他建立的單元組是樹狀的。上述這兩種方法擁有“綜合工具”類方法的共同點(diǎn)，就是在提取規(guī)則性信息時要求回溯到綜合階段以前的硬件描述語言中，從中得到大多數(shù)信息。但是，在大多數(shù)實際情況中，布局算法的輸入是純粹的綜合后的電路網(wǎng)表，并沒有初始硬件描述，原有的規(guī)則性信息在綜合后都丟失了，這類算法在這種情形下幾乎不再適用?！疤崛」ぞ摺鳖愃惴ㄇ『孟喾?，它是在電路網(wǎng)表中通過一定的提取算法進(jìn)行規(guī)則性信息的提取，而不需要電路綜合前的硬件描述信息，因而特別適用于一般意的datapath單元布局。R.X.T. Nijssen提出了一種基于單元連接關(guān)系分析的提取算法，該算法通過分析單元連接度和數(shù)據(jù)流向等電路屬性來判斷單元之間的關(guān)系，并據(jù)此提取規(guī)則單元。國內(nèi)清華大學(xué)的博士也提出了一種基于單元規(guī)則排列的datapath布局算法（DPP）能夠保持bit slice結(jié)構(gòu)，并且能夠提高功率和減小布局面積，還可以結(jié)合到任何P&R工具當(dāng)中，算法提出了一個新的不規(guī)則度（irregularity degree）模型來衡量單元之間連接關(guān)系的規(guī)則性，并根據(jù)這個模型提出了規(guī)則提取算法，由提取算法抽取的規(guī)則單元排列成矩陣，最后算法把規(guī)則矩陣轉(zhuǎn)化為并行約束并通過二次布局算法實現(xiàn)了datapath單元布局。

2 datapath結(jié)構(gòu)特點(diǎn)

Datapath是并行進(jìn)行多位數(shù)操作的數(shù)字集成電路，其在邏輯上和物理結(jié)構(gòu)上具有規(guī)則性，與隨機(jī)邏輯單元（即控制邏輯單元）不同，它經(jīng)常用于算術(shù)邏輯單元，每一個操作會和一個功能塊相關(guān)，如圖1所示?？蛻舻囊蟛煌?，功能塊就不同，一般有加法器、寄存器族、觸發(fā)器、多路選擇和多路控制器、譯碼器、解碼器、比較器等。位之間的連接是由操作定義的，因此，電路中存在兩種意義上的互連流，一種是數(shù)據(jù)流，一種是控制流。數(shù)據(jù)流一般是并行的多位數(shù)據(jù)?？刂屏骺梢允侨值目刂菩盘枺瑢γ恳晃煌瑫r產(chǎn)生作用；也可以是局部的控制信號，控制相鄰幾位，如圖2所示。

在標(biāo)準(zhǔn)單元模式的布局背景下，根據(jù)操作的數(shù)據(jù)位數(shù)，datapath的功能塊被設(shè)計成相應(yīng)個數(shù)的標(biāo)準(zhǔn)單元，每個單元負(fù)責(zé)一個數(shù)據(jù)位上的操作，相同功能塊的單元形成列狀排列的叫“列（word-line）”；一個列中的單元之間多通過控制線相連，不同功能塊里對相同的位進(jìn)行操作的單元可以排列成行叫“行（slice）”，相同行中的單元之間多通過數(shù)據(jù)線相連。這樣，datapath電路在設(shè)計時就被看成是按行和列結(jié)構(gòu)規(guī)則排列的單元矩陣，這個矩陣稱為“規(guī)則矩陣”，矩陣中的單元稱為“規(guī)則單元”，而datapath電路中規(guī)則單元成矩陣排列的這種特殊結(jié)構(gòu)被稱為bit-slice結(jié)構(gòu)。圖1為一個datapath電路的邏輯設(shè)計結(jié)構(gòu)，圖2為相應(yīng)的成矩陣狀排列的物理布局結(jié)構(gòu)，這也是datapath電路最理想的布局結(jié)果。

如圖3所示，正因為datapath電路的bit-slice結(jié)構(gòu)具有高度的規(guī)則化和結(jié)構(gòu)化，吸引了設(shè)計者們想要以規(guī)則化的布局方式達(dá)到高性能、布局面積小的目的。每一組功能相近的組件被稱為datapath的一個stage，如圖3，頂部的一組datapath組件也可以分為幾個stage，電路的數(shù)據(jù)流向一般與stage順序方向一致，但是stage內(nèi)部也可以有自己的數(shù)據(jù)流向，如stage3，在位列之間也會有數(shù)據(jù)流，如stage2，一個stage到下一個stage之間，可以有一對多或多對一的輸入輸出關(guān)系。這種規(guī)則化的原理圖一般可以整體轉(zhuǎn)化為一個規(guī)則化的布局。在特殊情況下，數(shù)據(jù)流可能會很長，以至于無法形成一個簡單規(guī)則的bit-slice結(jié)構(gòu)，我們在布圖當(dāng)中就會解決這個問題。

3 datapath電路的布局要求

Datapath對布局的要求源于其自身的電學(xué)性能的要求。由于datapath電路一般由幾百至幾千個標(biāo)準(zhǔn)單元組成，規(guī)模較小，較一般芯片來說單元數(shù)量少，所以對線長的要求并不十分高。但由于datapath模塊在整個芯片里承擔(dān)主要的計算任務(wù)，因此對最大時延、串?dāng)_、信號時延平衡等性能指標(biāo)的要求相對較高。其中時延是指信號到達(dá)一個單元的時間與要求時間的最大延遲，信號時延平衡則指同一信號到達(dá)同一功能塊中不同位上的單元的時延差異，可以通過計算信號到達(dá)同一列上不同單元的延遲的最大、最小值的比值來大致衡量。對于最大時延的優(yōu)化有已經(jīng)很多文獻(xiàn)研究，但對于信號時延平衡到目前并沒有找到很好的數(shù)學(xué)模型，解決起來比較困難。但是，人們在長期的設(shè)計實踐中發(fā)現(xiàn)：如果datapath單元的布局能夠參考設(shè)計時給出的規(guī)則化的bit-slice結(jié)構(gòu)，那么線網(wǎng)互聯(lián)的延時將會得到改善，這是由于布局的過程從很大程度上借鑒了datapath電路本身的特點(diǎn)，datapath電路中比例最大的數(shù)據(jù)線（比如Bus線網(wǎng)）將最大程度的分布在行內(nèi)，減少了線網(wǎng)在行與行之間的交疊；同時，由于行與行之間的相似性，類型相同的線網(wǎng)在長度和信號方向上都相差無幾，這對減少信號偏差、降低串?dāng)_無疑十分有利，由此得到的布局結(jié)果往往能在最大時延和時延平衡性方面都獲得良好的效果。另一方面，由于布局結(jié)果與datapath設(shè)計的拓?fù)浣Y(jié)果十分一致，這將有利于設(shè)計者在綜合階段就能對datapath電路的時延等性能指標(biāo)做出比較精確的估計，從設(shè)計的整體過程上提高電路的質(zhì)量。也就是說：datapath電路特殊的結(jié)構(gòu)和性能要求我們在布局過程中要使datapath電路能夠很好的實現(xiàn)單元的規(guī)則化排列。

4 datapath電路布局的基本方法

Datapath電路的布局方法一般分為兩個步驟，第一部是提取規(guī)則單元，第二布是規(guī)則單元布圖規(guī)劃。

4.1 規(guī)則單元的提取

實現(xiàn)單元規(guī)則化排列首先要掌握單元的規(guī)則性信息，即如何區(qū)分規(guī)則單元和自由單元，以及區(qū)分規(guī)則單元與在規(guī)則矩陣中相鄰的其他單元之間的位置關(guān)系等。正常情況下，結(jié)構(gòu)規(guī)則的邏輯單元一般都出現(xiàn)在datapath組件里，目前主要有兩種提取規(guī)則單元的方法：一是覆蓋，在所有可能要用的模塊當(dāng)中提取所有功能和結(jié)構(gòu)相似的模塊，然后選出最好的映射在電路當(dāng)中。二是膨脹，發(fā)現(xiàn)相鄰位塊之間有相似的邏輯或結(jié)構(gòu)的一部分邏輯門作為模板，再將周圍電路與之前的模板進(jìn)行比較，看是否具有相似的規(guī)則化，如果不規(guī)則度小于一定閾值的，則可以把模板擴(kuò)大，繼續(xù)膨脹找到相似結(jié)構(gòu)，如果不規(guī)則度太大，則停止膨脹，得到最后相關(guān)的規(guī)則電路。

4.2 規(guī)則電路的布圖規(guī)劃

Datapath的布圖規(guī)劃就是要給datapath組件找到合適的相對位置，同時依據(jù)數(shù)據(jù)流的方向。其目的就是要實現(xiàn)在沒有重疊布局的前提下，布圖面積和互連線長達(dá)到最優(yōu)化的結(jié)果。Datapath的布圖規(guī)劃最大的特點(diǎn)是線網(wǎng)的大多數(shù)是總線并且與數(shù)據(jù)流的方向一致。當(dāng)數(shù)據(jù)流長度過大時，有兩種方法解決，一種方法是把較長的為線分為幾個部分然后把他們依次布局在電路中，以最大寬度和高度為約束，找到最優(yōu)的分解辦法和布圖方式，如圖4（a）；另一種方法是用般的模塊封裝的算法并且把數(shù)據(jù)流方向的約束加上，確保每一級的操作都是按順序的，如圖4（b）。

參考文獻(xiàn)

[1]Terry Tao Ye and Giovanni De Micheli.Data Path Placement with Regularity[C].In Proceedings of ICCAD 2000.

[2]A. Chowdhary，S.Kale，P.Saripella，N. Sehgal and R.Gupta.A General APProach for Regularity Extraction in DatapathCircuits[C].International Conference on Computer-Aided Design，1998.

[3]R.X.T.Nijssen and C.A.J.vanEijk， “GreyHound：A methodology for utilizing datapath regularity in standard design flows”，Integration， the VLSI Journal 25，1998：111-135.

[4]楊長旗.超大規(guī)模集成電路混合模式布局算法研究和系統(tǒng)設(shè)計[D].清華大學(xué)博士論文，2004.

[5]L.Scheffer， L.Lavagno and G.Martin，eds.，EDA for IC Implementation， Circuit Design， and Process Technology[M]， CRC Press， Boca Raton，2006.

[6]Ulf J?lmbrant and MattiasWinsten.Structured Digital Design.CiteSeerx， Scientific Literature Digital Library and Search Engine[J].version 1.02，2007：1-4.

作者簡介

郝燕芳（1990-），女，山西省晉中市人?，F(xiàn)為中國礦業(yè)大學(xué)（北京）碩士研究生。研究方向為計算機(jī)系統(tǒng)結(jié)構(gòu)、集成電路。

作者單位

中國礦業(yè)大學(xué)（北京） 北京市 10083