Persons
Article author
Currently, the methods based on a Boolean satisfiability (SAT) problem are one of the efficient approaches to solving the problem of Boolean matching and the equivalence checking of digital circuits. In combination with classic routing algorithms and optimization techniques, the SAT methods demonstrate the results exceeding the classic routing algorithms by the operation speed and the quality of obtained results. In the paper, the analysis of the modern practice of using the SAT methods in the CAD systems for VLSI has been performed. The examples of modern SAT approaches to the problems of the formal equivalence checking of digital circuits descriptions within the technological mapping framework and to the routing problem as a part of the FPGA design flow have been considered. The algorithm of the detailed routing of the FPGA switching blocks using the satisfiability problem has been developed and presented. The results of its work have been demonstrated on the example of the programmable logic block of the domestic made integrated circuit 5400TP094. The block has the island architecture, where the configurable logic blocks and switching blocks form a regularly repeated layout template. The properties of the chosen classic architecture permit to expand the region of presented algorithm to the entire class of island style FPGA. The algorithm has been tested on the project benchmarks ISCAS-85, ISCAS-89 and LGSynth-89. The comparison of the developed SAT-based algorithm with the well-known routing algorithm Pathfinder by criteria of the elapsed time and the achieved portion of routed nets in the switching blocks is presented. It has been determined that the considered Boolean satisfiability methods for the routing problem are capable to prove the circuit unroutability, unlike the algorithm Pathfinder which results can only implicitly indicate it. The paper demonstrates that the application of more efficient SAT solver significantly accelerates work of the suggested detailed routing algorithm.
- Counter: 736 | Comments : 0
The parallel architectures of computing systems, including the massively parallel ones, attract a particular interest of modern researchers in the theoretical informatics field. In this connection the hardware or algorithmic acceleration of the interprocessor exchange becomes the main objective. One of the approaches to creation of algorithms can be the use of nonconventional formalism-neural networks or cellular automata (CA), to realize the model of near interaction of elementary calculators. In the work three operations with matrix data have been considered: unary, reflection, transposing. The operations have been realized by parallel algorithms in the formalism of the cellular automata in an assumption that the data had been loaded into CA before the calculation. It has been shown that all presented algorithms have linear complexity of the matrix size. Movement and modification of the data have been executed by means of introducing the bit or/and trit flag components into a cell state description. The calculation stop-conditions are the occurrence of a stop-condition of a special CA cell or of all cells of the CA field, i.e. their «freezing». The development of the cellular automata algorithmization on an example of elementary operations over matrices can be used as a base for solving more difficult tasks (for example, the calculations of a determinant of a matrix).
- Counter: 1971 | Comments : 0
One of the main advantages of FPGA and CPLD is the high development speed; therefore, the importance of effective computer-aided design tools for modern microcircuits of these classes cannot be overestimated. Placement and routing are the most time-consuming stages of FPGA/CPLD design flow. The quality of results of these stages is crucial to the final performance of custom digital circuits implemented on FPGA/CPLD. The paper discusses an approach to accelerating the routing stage within the layout synthesis flow for FPGA/CPLD by introducing a few algorithmic improvements to a routing procedure. The basic routing algorithm under study is a modified Pathfinder for a mixed routing resource graph. Pathfinder is a well-known negotiation-based routing algorithm that works on the principle of iteratively eliminating congestions of chip routing resources. For experiments, the sets of test digital circuits ISCAS'85, ISCAS'89, LGSynth'89 and several custom industrial projects were used. The impact of the proposed algorithmic improvements was analyzed using four FPGA/CPLD architectures. It has been established that due to the improvements of the algorithm proposed in the paper, the average reduction in routing time was from 1.3 to 2.6 times, depending on the FPGA/CPLD architecture, with no significant negative effect on the timing characteristics of the designed circuits.
- Counter: 538 | Comments : 0
The cellular automata formulations of the algorithm for sorting arrays of characters and strings, not available in literature of recent decades, have been presented. For the first time, the cellular automation, that multiplies two integers written in a number system with an arbitrary basis, has been proposed. The algorithm is based on the Atrubin’s scheme for parallel multiplication by means of a symbolic array of processors and requires four components (registers) instead of five.
- Counter: 1828 | Comments : 0