Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 141
Issue 6
IEE Proceedings - Computers and Digital Techniques
Volume 141, Issue 6, November 1994
Volumes & issues:
Volume 141, Issue 6
November 1994
-
- Author(s): P. Montuschi ; L. Ciminiera ; A. Giustina
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 317 –324
- DOI: 10.1049/ip-cdt:19941386
- Type: Article
- + Show details - Hide details
-
p.
317
–324
(8)
The advantages of the convergence with the square of the Newton-Raphson method are combined with the precision characteristics of digit-by-digit algorithms to obtain units for fast division that satisfy the IEEE 754 floating point standard requirements. A general design methodology that leads to a class of alternative architectures providing interesting performances for division is presented, together with one example of possible implementation. In particular, the proposed implementation achieves a speedup varying from 20% to about 30% in comparison with a previous architecture by Fandrianto, with a relatively small additional hardware cost if a multiplier is already available on the arithmetic unit. - Author(s): S.-M. Yen ; C.-S. Laih ; A.K. Lenstra
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 325 –326
- DOI: 10.1049/ip-cdt:19941271
- Type: Article
- + Show details - Hide details
-
p.
325
–326
(2)
In several cryptographic protocols the product of a small number of exponentiations is required, but the separate exponentiation results are not needed. A simultaneous exponentiation algorithm that takes advantage of this situation and that is substantially faster than the ordinary approach using separate exponentiations is presented. - Author(s): J. Jiang and S. Jones
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 327 –333
- DOI: 10.1049/ip-cdt:19941387
- Type: Article
- + Show details - Hide details
-
p.
327
–333
(7)
The paper presents a parallel algorithm design for real-time implementation of arithmetic coding. The implementation comprises a parallel-processing array arranged in a tree structure. Within each cycle, a group of input symbols can be encoded. This increases the arithmetic coding speed substantially. Details of a fixed-precision algorithm design, its implementation and simulation of its performance are reported. - Author(s): P. Srinivasan and F.E. Petry
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 334 –340
- DOI: 10.1049/ip-cdt:19941414
- Type: Article
- + Show details - Hide details
-
p.
334
–340
(7)
There exist many types of special-purpose systems that require rapid and repeated division by a set of known constant divisors. Numerous solutions have been proposed in response to the deficiencies of the conventional division algorithms for applications which involve repeated divisions by known constants. Six approaches are reviewed in detail and their relationships are shown by reducing them to equivalent forms. Proving the equivalence of these algorithms allows them to be considered as alternative implementations of the same basic function. Proof of correctness of one form serves to verify all the methods. The analytical process has led to an improved understanding of constant division and of the division operation in general. It has provided a foundation for further analysis and algorithm development, including the establishment of the theoretical basis of quotient and remainder generation, a generalised implementation of division by divisors 2n±1, and extension of this method to divide by small integers by generating the value of the B-sequence, the value in one period, of the integer reciprocal. - Author(s): J.J. Harms and J.W. Wong
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 341 –346
- DOI: 10.1049/ip-cdt:19941292
- Type: Article
- + Show details - Hide details
-
p.
341
–346
(6)
The performance of scheduling algorithms for a reservation system is investigated. In this system, a user request is characterised by its start time, resource requirement and holding time. Of interest are scheduling algorithms to handle user requests in a loss system where resource requirements may vary. A Markov decision process formulation is used to obtain the optimal scheduling decisions. Two special cases are considered in depth; they correspond to optimal algorithms that minimise the blocking probability and maximise the channel utilisation, respectively. Analytic results are also obtained for the blocking probability and channel utilisation for an arbitrary scheduling algorithm. Using these results, the performance of first come, first served (FCFS) and the two optimal algorithms is compared. We also prove that FCFS is optimal for maximising channel utilisation when the resource requirement follows a uniform distribution. - Author(s): F.P. Burns ; D.J. Kinniment ; A.M. Koelmans
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 347 –355
- DOI: 10.1049/ip-cdt:19941504
- Type: Article
- + Show details - Hide details
-
p.
347
–355
(9)
Transformational synthesis is the process of generating a hardware implementation from an initial behavioural description, by repeatedly applying transformations to the behavioural descriptions until a satisfactory implementation can be generated. Although it is essential to verify the correctness of the applied transformations, it is also very important to present the changes to the designer in an understandable form. A prototype interactive design tool has been implemented that allows easy use of a database of formally correct transformations. Its basic features are described, and its operation and interaction with the theorem prover are demonstrated with examples. - Author(s): C.-L. Wey ; N. Berthelot ; B. Veltkamp
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 356 –360
- DOI: 10.1049/ip-cdt:19941377
- Type: Article
- + Show details - Hide details
-
p.
356
–360
(5)
Rapid advancements in technology demand innovative computation algorithms and hardware structures to achieve high performance. High-speed dividers are commonly designed using SRT division methods. Recently, a high-speed carry-free divider design using redundant binary representation has been presented. Based on the carry-free division algorithm and a more general cell-fault model instead of stuck-at fault model, the paper presents a concurrent error detection scheme using alternating input data. The key to the detection of faults is determining that at least one input combination exists for which the error does not result in alternating outputs. Results show that, with a low hardware overhead, the divider circuit is capable of detecting single/multiple transient faults in one cell during the real-time operation and enhancing its reliability significantly. - Author(s): S. Chattopadhyay ; S. Roy ; P. Pal Chaudhuri
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 361 –368
- DOI: 10.1049/ip-cdt:19941509
- Type: Article
- + Show details - Hide details
-
p.
361
–368
(8)
Owing to their high degree of flexibility and low design-turnaround time, field-programmable-gate-array (FPGA) based designs are becoming very popular. With the availability of different types of FPGA, the need of a unified approach for logic-block-independent technology mapping is being felt increasingly. The paper presents a new approach to efficient realisation of a given combinational function in terms of a prespecified k-input-single-output logic block. All subfunctions of 1 to k inputs realisable by the logic block are generated and kept in a library. The approach is general in the sense that it is not targeted to any specific FPGA built around a specified set of basic blocks. It uses a node-clustering technique for breaking up the given combinational function into subfunctions with special treatment for the fanout nodes. The scheme utilises a novel signature-based strategy to find a match for a subfunction in the library. One contribution is the elegant signature-generation scheme that can be applied for any library-based search problem. The signature is unique for functions of up to four variables and has an aliasing of around 0.5% for functions with larger number of variables. For comparison with other mapping techniques, the KGPMAP algorithm has been applied to several combinational benchmark circuits using Actel's act1-library. The result has been found to be superior to other well known library-based technology mappers and some Actel-specific mappers. - Author(s): C.-C. Tsai and M. Marek-Sadowska
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 369 –374
- DOI: 10.1049/ip-cdt:19941505
- Type: Article
- + Show details - Hide details
-
p.
369
–374
(6)
A method for extracting the cubes of the generalised Reed-Muller (GRM) form of a Boolean function with a given polarity is presented. The method does not require exponential space and time complexity and it achieves the lower-bound time complexity. The proof of the method's correctness constitutes the first half of the paper. Also, a separate heuristic algorithm to find the optimal polarity that requires the least number of cubes in the GRM representation is proposed. The algorithm is fast and derives the polarity for variables and extracts all cubes simultaneously. It is based on the concept of a Boolean centre for vertices, which emulates the centre of gravity concept in geometry. The experimental results for the heuristic algorithm agree strongly with the authors observations and analysis. - Author(s): A.E. Bashagha and M.K. Ibrahim
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 375 –380
- DOI: 10.1049/ip-cdt:19941502
- Type: Article
- + Show details - Hide details
-
p.
375
–380
(6)
The paper presents a new digit-serial architecture for division and square-root which can be pipelined to the bit level to achieve high throughput. The architecture is different from the existing divider/square-root architectures in that it is based on the radix-2n algorithm. As a result, any type of adder can be used in the proposed digit-serial controlled add/subtract basic cell. The authors present two basic digit-serial controlled add/subtract cells. The first is based on the conventional carry feedback digit-serial adder. The second is based on the carry feed-forward adder, which results in the first reported digit-serial divider/square-root architecture that can be pipelined down to the bit-level. An evaluation of the proposed architecture for different values of the digit size is also presented. - Author(s): M.G. Parker and M. Benaissa
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 381 –390
- DOI: 10.1049/ip-cdt:19941527
- Type: Article
- + Show details - Hide details
-
p.
381
–390
(10)
This paper proposes design techniques for the efficient VLSI implementation of bit-serial multiplication over a modulus. These techniques reduce multiplication into simple cyclic shifts, where the number representation of the data is chosen appropriately. This representation will, in general, be highly redundant, implying a relatively poor throughput for the multiplier. It is then shown how, by splitting the multiplier into two pipelined multipliers, the throughput of the unit can be increased, whilst still retaining a cyclic-shift implementation. The split multiplier requires a mid-computation basis conversion, and the two number representations, used within the unit, are only moderately redundant. Thus, high-throughput, bit-serial multipliers are achieved, with most of the complexity contained within systolic basis converter modules. The multipliers are applicable to the VLSI implementation of high-throughput, signal processing operations performed over finite fields, in particular, transform and filter operations. - Author(s): N. Clarke and A. Cantoni
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 391 –397
- DOI: 10.1049/ip-cdt:19941515
- Type: Article
- + Show details - Hide details
-
p.
391
–397
(7)
Look-up tables are used extensively in telecommunications networks in such areas as multiplexing, switching, routing and reassembly. There are also many applications involving look-up tables outside the field of telecommunications, such as electronic dictionaries and database search algorithms. Essentially, look-up tables map sets of input numbers onto arbitrary sets of output numbers. The paper discusses two new methods for the design of high speed, dynamic look-up tables and compares them with other common look-up table implementations. - Author(s): R.-Y. Hwang and F. Lai
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 398 –404
- DOI: 10.1049/ip-cdt:19941519
- Type: Article
- + Show details - Hide details
-
p.
398
–404
(7)
Exploiting loop parallelism is an important way to enhance system performance. For loop-carried dependence, the original DO loop is converted into a DOACROSS loop to function concurrently. In general, synchronisation operations are inserted to maintain order dependence during parallel execution. For each processor in a shared memory multiprocessor, if the executing sequence is the same as the original source program, the action of synchronisation operation is correct; however, if each processor is used out of order, such as in the superscalar machine, the action of synchronisation operation may be incorrect. The synchronisation marker insertion method proposed resolves this problem in two steps: (i) proper synchronisation markers are appended into the array element of dependences, and (ii) synchronisation markers are generated during intermediate code generation. Finally, algorithms are proposed to prevent error during instruction scheduling. - Author(s): K. Bilinski ; M. Adamski ; J.M. Saul ; E.L. Dagless
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 405 –412
- DOI: 10.1049/ip-cdt:19941508
- Type: Article
- + Show details - Hide details
-
p.
405
–412
(8)
The paper presents new algorithms for the synthesis of parallel controllers which operate on a Petri net. This net is first simplified by reduction, then coloured and finally used to generate a state assignment with which the controller can be synthetised. The new concept of using colours for detecting and representing concurrency within the Petri net is presented. Experimental results show that the methods presented are especially economical for the synthesis of complex controllers. - Author(s): S.-J. Chen ; C.-C. Tsai ; Y.-L. Chen ; Y.-H. Hu
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 6, p. 413 –420
- DOI: 10.1049/ip-cdt:19941160
- Type: Article
- + Show details - Hide details
-
p.
413
–420
(8)
A general area router (GEAR) based on the planning approach is proposed and implemented. Two meta-planning techniques, graceful retreat and least impact, are used to manage the selection of net segments and the assignment of track resources. Apart from the novel application of these planning techniques, we have also consolidated many effective routing heuristics into GEAR so that it is able to solve a variety of difficult routing problems. These include channel routing, switchbox routing, staircase routing, rectilinear area routing with obstacles, and other general area routing problems. Extensive simulation results indicate that GEAR is very competitive compared with the best known special-purpose routers.
Division unit with Newton-Raphson approximation and digit-by-digit refinement of the quotient
Multi-exponentiation (cryptographic protocols)
Parallel design of arithmetic coding
Constant-division algorithms
Performance of scheduling algorithms for channel reservation
Stride: a tool for formal interactive system synthesis
Concurrent-error detection in high-speed carry-free dividers
KGPMAP:library-based technology-mapping technique for antifuse based FPGAs
Minimisation of fixed-polarity AND/XOR canonical networks
Radix digit-serial pipelined divider/square-root architecture
VLSI structures for bit-serial modular multiplication using basis conversion
Implementation of dynamic look-up tables
Guiding instruction scheduling with synchronisation markers on a superscalar based multiprocessor
Petri-net-based algorithms for parallel-controller synthesis
General area router based on planning techniques
Most viewed content for this Journal
Article
content/journals/ip-cdt
Journal
5
Most cited content for this Journal
We currently have no most cited data available for this content.
