PDF《第14 卷第3期》

第14 卷第3期太赫兹科学与电子信息学报 Vo1.

14, No.

3 2016 年6月Journal of Terahertz Science and Electronic Information Technology Jun. ,

2016 文章编号:2095-4980(2016)03-0474-07 Evaluating logic functionality of cascaded fracturable LUTs GUO Zhenhonga,b ,LIN Yua ,LI Tianyia ,JIA Ruia,b ,GAO Tongqianga ,YANG Haiganga (a.Institute of Electronics;

b.University of Chinese Academy of Sciences,Chinese Academy of Sciences,Beijing 100190,China) Abstract: Look Up Tables(LUTs) are the key components of Field-Programmable Gate Arrays(FPGAs). Many LUT architectures have been studied;

nevertheless, it is difficult to quantificationally evaluate an LUT based architecture. Traditionally, dedicated efforts on specific modifications to the technology mapping tools are required for LUT architecture evaluation. A more feasible evaluation method for logic functionality is strongly required for the design of LUT architecture. In this paper, a mathematical method for logic functionality calculation is proposed and conventional and fracturable LUT architectures are analyzed. Furthermore, a cascaded fracturable LUT architecture is presented, which achieves twice logic functionality compared with the conventional LUTs and fracturable LUTs. Key words:Field Programmable Gate Array;

cascaded Look Up Tables;

functionality evaluation CLC number: TN79 Document code: A doi: 10.11805/TKYDA201603.0474 LUT based FPGAs have been one of the most popular digital logic implementation media in various application domains over last decade. However, the search of new FPGA architecture remains a continuing area of research [1] . The crucial goal of these researches is the reduction of the delay, area, and power consumption, and improvement of resource utilization, routability and logic functionality of the programmable logic. Reducing delay quantificationally is especially important as it facilitates high frequency implementation on FPGAs. In modern FPGAs, the delay is dominated by interconnects [2-3] . Modern FPGAs fracture a LUT into several sub-LUTs in order to achieve more flexible inputs and outputs, and improve logic functionality [4-6] , however, later discussion will show that more inputs cause an exponential increase in LUT area. Another method is to add inter-LUT connections, where a LUT'

s output connects to another LUT'

s input via a dedicated interconnect, to avoid going through the large multiplexer before each LUT and the channels outside the logic cluster [2] . Combining the advantages of fracturable and cascaded LUTs, a new cascaded fracturable LUT architecture is proposed. The proposed LUT works as a fracturable LUT in fracturable mode. While in cascaded mode, the fractured sub-LUTs are cascaded, in order to implement different logic functionality. An SRAM controlled multiplexer is used to switch between the two modes, and a feedback path is added for cascading the sub-LUTs, which will have a negligible cost in delay and area. Traditionally, dedicated efforts on specific modifications to the technology mapping and packing tools are required for LUT architecture evaluation [2,7-8] . In this paper, a mathematical method for logic functionality calculation is proposed. Our evaluation method shows that the proposed architecture implements twice logic functionality of conventional LUTs and fracturable LUTs.

1 Conventional LUT In this section, a new method is employed to evaluate logic functionality of convention LUT. The definition of logic functionality and minterm used in our evaluation method refers to [9-10]. In Fig.1, conventional K-input LUT has K inputs and one output, which are represented by xi,i=1,2,…,K, and y, respectively. The LUT includes a 2K -input multiplexer(2K -MUX). The K inputs act as control signals of the 2K -MUX. The inputs of the 2K -MUX are provided by Received date:2014-12-01;

Revised date:2015-03-08 Fund project:supported by National Science and Technology Major Project of China(No. 61404140,61106033) Fig.1 Conventional LUT … x0 x1 xK y K-LUT 第3期GUO Zhenhong,et al: Evaluating logic functionality of…

475 SRAM cells. So, the logic function of output y, F(y), can be formulated as following:

0 1

2 1

1 2

1 2

1 2

1 1

2 2

1 ( ) K K K K K K K F y x x x x x x x x x x x x x x α α α α ? ? ? 1) where i α , 0,1, ,

2 1 K i = ? , are SRAM configuration bits. ( ) F y is denoted to be the number of logic functions of F(y). Because there are 2K configuration bits, the number of logic functions that conventional LUT can realize is

2 2 K according to Theorem 1. So the below equation is obtained:

2 ( )

2 K F y = (2) As the number of inputs, K, increases, the number of SRAM cells will increase exponentially, leading to a huge increase in area. Meanwhile, in practical applications, mapping logic circuits to a LUT with large number of inputs will cause lots of SRAM resources wasted.

2 Fracturable LUT In this section, the proposed method is extended to evaluate logic functionality of fracturable LUT. In order to increase the number of inputs and outputs, a K-LUT can be fractured into two (K-1) input sub-LUTs. The inputs of fracturable LUT are increased from K to 2K-1, and the output number is increased by 1. Each sub-LUT has

1 2 K ? SRAM cells, and total SRAM resources remain the same. When inputs of fracturable LUT are less than 2K, some inputs are shared by the two sub-LUTs. The range of the number of shared inputs, marked as I, is from

0 to K-1. As in Fig.2, xi, i=1,2,…,I, are shared inputs, and j i x , 1, ,

1 i I K = + ? , 0,1 j = , are exclusive inputs. Each of the two sub-LUTs has its own output y0 and y1 . When the fracturable LUT is used as two (K-1)-input sub-LUTs, each of them can implement

1 2

2 K? logic functions. The logic functions of output yj , j=0,1, are represented as following: ( ) ( ) ( ) ( )

1 1

1 1

1 1

0 1

1 1

1 2

1 1

1 1

1 1

2 2

1 1

1 1

1 1

1 2

2 2

1 K I K I K K I K j j j j j j j K I I I K I K j j j j j j I I I K I K j j j j j j I I I K I K F y x x x x x x x x x x x x x x x x x x x x α α α α α α ? ? ? ? ? ? ? ? ? + ? + ? ? ? ? = + + + + + + + + + (3) Theorem 1: Two sub-LUTs with I shared inputs implement

2 2 I same logic functions. From Theorem 1, the total number of same logic function of ( )

0 F y and ( )

1 F y , represented by ( ) ( )

0 1 F y F y ∩ , is

2 2 I . So,

1 0

1 2

0 1

2 2 ,

2 K I F y F y F y F y ? 4) Furthermore, the two sub-LUTs can be merged by a 2-input multiplexer to generate output y. The number of logic functions that output y can realize is

2 2 K .

2 ( )

2 K F y = (5) Therefore, no matter how many inputs, the number of logic functions of output y does not change. For output y of fracturable LUT, the number of logic functions is equal to the output of conventional LUT. However, the logic functions of the two LUT architectures are different. Conventional LUT can implement all combinational logic functions of the K inputs, however, fracturable LUT can only implement part of logic functions of all inputs. Fig.2 Fracturable LUT with shared inputs

1 x

0 1 I x +

0 1 K x ?

1 1 K x ? … … …

1 1 I x + I x …

2 x

1 x

2 x I x (K-1)-LUT

0 (K-1)-LUT

1 y0 y1 y

0 1 s

476 太赫兹科学与电子信息学报 第14 卷2()2KFy=(6)

3 Cascaded Fracturable LUT Although fracturable LUT has more inputs and outputs compared to conventional LUT, the two architectures can implement same number of logic functions. In this section, a cascaded fracturable LUT architecture is proposed and its architecture is shown in Fig.3. Compared with fracturable LUT in Fig.2, an SRAM-controlled multiplexer and a feedback path from output of LUT0 to input of LUT1 are added. By configuring the multiplexer, the proposed architecture works in two different modes, fracturable mode and cascaded mode. In fracturable mode, input

1 1 x of LUT1 is used and the feedback path is not activated, the proposed architecture acts as same as a fracturable LUT. In cascaded mode, output y0 of LUT y1 is used as one input to LUT1, and a LUT chain is constructed. In the following, the logic functionality of cascaded mode and fracturable mode of proposed architecture is analyzed. 3.1 Cascaded Mode In cascaded mode, the total number of external inputs is 2K-2 as in Fig.4, where I=0 meaning no shared inputs. LUT0 has K-1 external inputs, represented by

0 i x , 1, 2, ,

1 i K = ? , while LUT1 has K-2 external inputs,

1 i x , 2,3, ,

2 i K = ? . And y0 and y1 represent the output LUT0 and LUT1 respectively, and y0 is connected to the input of LUT1. s acts as the selection signal of the multiplexer. The logic functions of output y1 and y can be formulated as following:

1 0

1 0

1 '

'

'

F y F y F y F y F y = + (7)

0 0

1 0

1 '

'

'

F y sF y sF y F y sF y F y = + + (8) where ( ) ( ) ( )

1 2

2 1

0 0

0 0

0 0

0 0

1 1

1 1

2 1

1 1

1 1

1 0

0 0

2 1

2 1

2 1

1 1

1 1

1 0

0 2

1 2

1 2

2 1 '

K K K K K K K K K K F y x x x x F y x x x x F y x x x x α α α α α α ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = + + = + + = + + . Theorem 2: The logic functions y1 and y are

1 0

1 0

1 0

0 1

0 1 '

'

'

'

'

'

F y F y F y F y F y F y sF y sF y F y sF y F y ? = + ? ? ? ? = + + ? ? , ( )

0 F y , ( )

1 '

F y and ( )

1 F y are the sum of products. ( )

0 F y has N0 configuration coefficients and N0 complete minterms. Each of ( )

1 '

F y and ( )

1 F y has N1 configuration coefficients. ( )

1 '

F y and ( )

1 F y have same minterms but different configuration coefficients. In each of, ( )

0 F y , ( )

1 '

F y and ( )

1 F y , only one product is

1 for any combination of its corresponding configuration coefficients. s denotes an input signal. Then the number of logic functions of y1 and y are ( ) ( )

0 1

1 1

0 1

1 2

1 2

2 2

2 2

2 /

2 2

2 2

2 2 N N N N N N N F y F y = + ? ? = * + ? ? ? ? ? ? . Fig.3 Proposed architecture: cascaded fracturable LUT … …

1 1 x

1 2 x

1 1 K x ?

0 1 x

0 2 x

0 1 K x ? s y0 y1 y

0 1 (K-1)-LUT

0 (K-1)-LUT

1 第3期GUO Zhenhong,et al: Evaluating logic functionality of…

477 In Equation

7 and Equation 8, ( )

0 F y , ( )

1 '

F y and ( )

1 F y have

1 2 K ? ,

2 2 K ? and

2 2 K ? configuration coefficients, respectively. From Theorem 2, th........