Ecole Polytechnique Federale De Lausanne

University of Utah Research Foundation

Giovanni De Micheli

Pierre-Emmanuel Julien Marc Gaillardon

Xifan Tang

Yusuf Leblebici

Luca Gaetano Amarù

Davide Sacchetto

David Atienza Alonso

Srinivasan Murali

Luca Benini

Edouard Giacomin

Michele De Marchi

Luca Gaetano Amaru

Federico Angiolini

Gain Kim

Pierre-Emmanuel Gaillardon

Pierre-Emanuel Gaillardon

Luca Gaetano Amarú

Pierre-Emmanuel Julien Gaillardon

Shashi Kanth Bobba

Tugba Demirci

A method for optimizing an implementation of a logic circuit, comprising steps of providing an interpretation of the logic circuit in terms of 3 Boolean variable majority operators M, with each of the majority operators being a function of a plurality of variables that returns a logic value assumed by more than half of the plurality of variables, and a single Boolean variable complementation operator '. The method further comprises providing a commutativity, a majority (&#x3a9;.M), an associativity (&#x3a9;.A), a distributivity (&#x3a9;.D), an inverter propagation (&#x3a9;.I), a relevance (&#x3a8;.R), a complementary associativity (&#x3a8;.C), and a substitution (&#x3a8;.S) transformation; and combining the &#x3a9;.M, &#x3a9;.C, &#x3a9;.A, &#x3a9;.D, &#x3a9;.I, &#x3a8;.R, &#x3a8;.C and &#x3a8;.S transformations to reduce an area of the logic circuit via (i) a reshaping procedure consisting of the &#x3a9;.A, &#x3a9;.C, &#x3a9;.D, &#x3a9;.I, &#x3a8;.R, &#x3a8;.S and &#x3a8;.C transformations, applied either left-to-right or right-to-left moving identical or complemented variables in neighbor locations of the logic circuit, (ii) an elimination procedure consisting of the &#x3a9;.M transformation, applied left-to-right, and the &#x3a9;.D transformation, applied right-to-left, that simplify redundant operators, or (iii) an iteration of steps (i) and (ii) till a reduction in area is achieved.

Majority logic synthesis

We present a Boolean logic optimization framework based on Majority-Inverter Graph (MIG). An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. Current MIG optimization is supported by a consistent algebraic framework. However, when algebraic methods cannot improve a result quality, stronger Boolean methods are needed to attain further optimization. For this purpose, we propose MIG Boolean methods exploiting the error masking property of majority operators. Our MIG Boolean methods insert logic errors that strongly simplify an MIG while being successively masked by the voting nature of majority nodes. Thanks to the data-structure/methodology fitness, our MIG Boolean methods run in principle as fast as algebraic counterparts. Experiments show that our Boolean methodology combined with state-of-art MIG algebraic techniques enable superior optimization quality. For example, when targeting depth reduction, our MIG optimizer transforms a ripple carry adder into a carry look-ahead one. Considering the set of IWLS'05 (arithmetic intensive) benchmarks, our MIG optimizer reduces by 17.98% (26.69%) the logic network depth while also enhancing size and power activity metrics, with respect to ABC academic optimizer. Without MIG Boolean methods, i.e., using MIG algebraic optimization alone, the previous gains are halved. Employed as front-end to a delay-critical 22-nm ASIC flow (logic synthesis+physical design) our MIG optimizer reduces the average delay/area/power by (15.07%, 4.93%, 1.93%), over 27 academic and industrial benchmarks, as compared to a leading commercial ASIC flow.

Boolean logic optimization in majority-inverter graphs

Resistive random access memory (RRAM) based multiplexers and field programmable gate arrays (FPGAs) are provided. The RRAM-based multiplexers and FPGAs include a 4T1R programming structure to program the RRAMs. The programming structure includes two programming transistors connected between the power supply and the top electrode of the RRAM and two programming transistors connected between the power supply and the bottom electrode of the RRAM. The programming transistors are used to set and rest the RRAMs. In the RRAM-based multiplexer programming transistors connected to the bottom electrodes are shared between a plurality of RRAMs. The shared programming transistors and an output inverter of the RRAM are provided in a deep N-well of the RRAM-based multiplexer. The programming transistors connected to the top electrodes of the RRAMs and a plurality of input inverters are provided in a regular well of the RRAM-based multiplexer.

Resistive random access memory based multiplexers and field programmable gate arrays

A routing architecture for fast interconnections between Look-Up Tables (LUTs) in a group of Basic Logic Elements (BLEs), whereby a size of the group ranges from 1 to k+1, where k is the number of inputs of a LUT, and LUTs in the group are indexed from 1 to k+1, and whereby (a) an output of a LUT, 1&#x2264;i&#x2264;k, connects to one of the inputs of routing multiplexers of LUT, i&#x3c;j&#x2264;k+1, hence creating a fast interconnection between LUTs, each routing multiplexer of LUT, 2&#x2264;m&#x2264;k+1, has only one input that is connected to the output of an other LUT, the output of LUTbeing devoid of any connection to any one of the inputs of the routing multiplexers; (b) a subset of the inputs of LUTare connected to the outputs of other LUTs by means of fast interconnections, leaving the remaining inputs of LUTfree of any fast interconnection, whereby for LUT, 2&#x2264;p&#x2264;k+1, p&#x2212;1 inputs of the LUTare connected to the outputs of LUT, 1&#x2264;q&#x2264;j, by means of fast interconnections; and (c) a cluster-based logic block contains at least one group of LUTs.

Pattern-based FPGA logic block and clustering algorithm

A method for transforming a tautology check of an original logic circuit into a contradiction check of the original logic circuit and vice versa comprises interpreting the original logic circuit in terms of AND, OR, MAJ, MIN, XOR, XNOR, INV original logic operators; transforming the original circuit obtained from the interpreting, into a dual logic circuit enabled for a checking of contradiction in place of tautology and vice versa, by providing a set of switching rules configured to switch each respective one of the original logic operators INV, AND, OR, MAJ, XOR, XNOR, MIN into a respective switched logic operator INV, OR, AND, MAJ, XNOR, XOR, MIN; and complementing outputs of the original circuit by adding an INV at each output wire. The method further provides testing in parallel the satisfiability of the original logic circuit, and the satisfiability of the dual logic circuit with inverted outputs. Responsive to one of the parallel tests finishing, the other parallel test is caused to also stop.

Method for speeding up boolean satisfiability

A bipolar resistive switching device (RSM device, FIG.) comprises an electrically conductive bottom electrode (BE, FIG.); a stack of transition metal oxides layers (RSM, FIG.), a number of transition metal oxide layers (RSO, FIG.) being equal or greater than 2, the stack comprising: at least one MOlayer (RSOA, FIG.), at least one oxygen gettering layer NO(RSOB, FIG.). The resistive switching device further comprises an electrically conductive top electrode (TE, FIG.).

Resistive switching element and use thereof

A Field Programmable Gate Array (FPGA) of the island-type comprising a plurality of cluster-based Configurable Logic Blocks (CLBs), whereby each of the cluster-based CLBs is surrounded by a global routing structure formed by a plurality of multiplexers and pass/transmission-gates organized in Switch Boxes (SBs) and Connection Blocks (CBs), the switch boxes and the connection blocks comprising at least a first plurality of resistive memories inserted in a data path of a first routing architecture of the switch boxes and the connection blocks. Each CLB contains Basic Logic Elements (BLEs), as well as local routing resources.

High-performance low-power near-Vt resistive memory-based FPGA

This invention describes a novel electronic device consisting of one&#x2014;or more&#x2014;vertically stacked gate-all-around silicon nanowire field effect transistor (SNWFET) with two independent gate electrodes. One of the two gate electrodes, acting on the central section of the transistor channel, controls on/off behavior of the channel. The second gate, acting on the regions in proximity to the source and the drain of the transistor, defines the polarity of the devices, i.e. p or n type. The electric field of the second gate acts either at the interface of the nanowire-to-source/drain region or anywhere in close proximity to the depleted region of the SiNW body, modulating the bending of the Schottky barriers at the contacts, eventually screening one type of charge carrier to pass through the channel of the transistor. This is achieved by controlling the majority carriers passing through the transistor channel by regulating the Schottky barrier thicknesses at the source and drain contacts.

Ambipolar silicon nanowire field effect transistor

A logic gate with three inputs A, B, and C, and one output implementing a function MAJ(A,B,C)=A*B+B*C+A*C comprising two mutually exclusive transmission gates (TGs) connected in series, based on two parallel double-gate controllable polarity devices, a polarity of each being controlled by input A and a conduction being controlled by input B, or vice-versa, in opposite polarities, and that route either an input A or C from one side of the transmission gates to the output.

Controllable polarity FET based arithmetic and differential logic

A method to design a Networks on Chips (NoCs)-based communication system for connecting on-chip components in a multicore system, said system comprising several elements communicating through the communication system, said communication system comprising at least switches, said method comprising the steps of modelling the applications running on the multicore system, establishing the number and configuration of switches to connect the elements, establishing physical connectivity between the elements and the switches, for each two pairs of communicating elements: (a) a defining a communication path, (b) calculating metrics as affected by the need to render said path into physical connectivity, taking into account any previously defined physical connectivity, (c) iterating the steps a and b for a plurality of possible paths, (d) choosing the path having the optimal metrics, and (e) establishing any missing physical connectivity between the switches so that the selected optimal path occurs across physically connected switches.

Method to design network-on-chip (NOC)-based communication systems

A method to provide reliability, power management and load balancing support for multicore systems based on Networks-on-Chip (NoCs) and to efficiently implement architectural support for this method by introducing complex packet handling mechanisms is achieved by modifying the basic network interfaces attached to the cores of multicore computation systems. It also proposes policies to leverage the proposed hardware extensions. This aim is achieved with a method to manage the load of peripheral elements within a multicore system comprising several processing units accessing peripheral elements through a NoC, each processing unit and peripheral element attached to a Network Interface in charge of formatting and driving the packets sent to or received from the NoC, wherein, while considering at least two peripheral elements having a similar function, the Network Interface dedicated to a first peripheral element reroutes the incoming packets to a second Network Interface dedicated to a second peripheral element.

Growing community of inventors

Lausanne, Switzerland

Giovanni De Micheli