This article describes the design and implementation of a novel compilation flow that implements circuits in FPGAs from a streaming programming language. The streaming language supported is called FPGA Brook and is based on the existing Brook language. It allows system designers to express applications in a way that exposes parallelism, which can be exploited through hardware implementation. FPGA Brook supports replication, allowing parts of an application to be implemented as multiple hardware units operating in parallel. Hardware units are interconnected through FIFO buffers which use the small memory modules available in FPGAs. The FPGA Brook automated design flow uses a source-to-source compiler, developed as a part of this work, and combines it with a commercial behavioral synthesis tool to generate the hardware implementation. A suite of benchmark applications was developed in FPGA Brook and implemented using our design flow. Experimental results indicate that performance of many applications scales well with replication. Our benchmark applications also achieve significantly better results than corresponding implementations using a commercial behavioral synthesis tool. We conclude that using an automated design flow for implementation of streaming applications in FPGAs is a promising methodology.

Capacity of FPGAs has grown significantly, leading to increased complexity of designs targeting these chips. Traditional FPGA design methodology using HDLs is no longer sufficient and new methodologies are being sought. An attractive possibility is to use streaming languages. Streaming languages group data into streams, which are processed by computational nodes called kernels. They are suitable for implementation in FPGAs because they expose parallelism, which can be exploited by implementing the application in FPGA logic. Designers can express their designs in a streaming language and target FPGAs without needing a detailed understanding of digital logic design. In this paper we show how the Brook streaming language can be used to simplify design for FPGAs, while providing reasonable performance compared to other methodologies. We show that throughput of streaming applications can be increased through automatic kernel replication. Using our compiler, the FPGA designer can trade off FPGA area and performance by changing the amount of kernel replication. We describe the details of our compiler and present performance and area of a set of benchmarks. We found that throughput scales well with increased replication for most applications.

There is an increasing need for automated conversion of high-level design descriptions into hardware. We present a flow that converts a software application written in the Brook streaming language into a hardware description targeting FPGAs. We use a combination of our source-to-source compiler and a commercial C2H behavioral synthesis compiler. Our approach results in a significant through-put increase compared to software and ordinary C2H results (up to 8.9X and 4.3X, respectively). The throughput can be further increased by using more hardware resources to exploit data parallelism available in streaming applications.

The growth in size and performance of field programmable gate arrays (FPGAs) has compelled system-on-a-programmable-chip (SoPC) designers to use soft processors for controlling systems with large numbers of intellectual property (IP) blocks. Soft processors control IP blocks, which are accessed by the processor either as peripheral devices or/and by using custom instructions (CIs). In large systems, chip multiprocessors (CMPs) are used to execute many programs concurrently. When these programs require the use of the same IP blocks which are accessed as peripheral devices, they may have to stall waiting for their turn. In the case of CIs, the FPGA logic blocks that implement the CIs may have to be replicated for each processor. In both of these cases FPGA area is wasted, either by idle soft processors or the replication of CI logic blocks. This paper presents a multithreaded (MT) soft processor for area reduction in SoPC implementations. An MT processor allows multiple programs to access the same IP without the need for the logic replication or the replication of whole processors. We first designed a single-threaded processor that is instruction-set compatible to Altera's Nios II soft processor. Our processor is approximately the same size as the Nios II economy version, with equivalent performance. We augmented our processor to have 4-way interleaved multithreading capabilities. This paper compares the area usage and performance of the MT processor versus two CMP systems, using Altera's and our single-threaded processors, separately. Our results show that we can achieve an area savings of about 45% for the processor itself, in addition to the area savings due to not replicating CI logic blocks

This paper presents preliminary work exploring adaptive field programmable gate arrays (AFPGAs). An AFPGA is adaptive in the sense that the functionality of subcircuits placed on the chip can change in response to changes observed on certain control signals. We describe the high-level architecture which adds additional control logic and SRAM bits to a traditional FPGA to produce an AFPGA. We also describe a synthesis method that identifies and resynthesizes mutually exclusive pieces of logic so that they may share the resources available in an AFPGA. The architectural feature and its associated synthesis method helps reduce circuit size by 28% on average and up to 40% on select circuits

In this paper, an iterative technology-mapping tool called IMap is presented. It supports depth-oriented (area is a secondary objective), area-oriented (depth is a secondary objective), and duplication-free mapping modes. The edge-delay model (as opposed to the more commonly used unit-delay model) is used throughout. Two new heuristics are used to obtain area reductions over previously published methods. The first heuristic predicts the effects of various mapping decisions on the area of the final solution, and the second heuristic bounds the depth of the mapping solution at each node. In depth-oriented mode, when targeting five lookup tables (LUTs), IMap obtains depth optimal solutions that are 44.4%, 19.4%, and 5% smaller than those produced by FlowMap, CutMap, and DAOMap, respectively. Targeting the same LUT size in area-oriented mode, IMap obtains solutions that are 17.5% and 9.4% smaller than those produced by duplication-free mapping and ZMap, respectively. IMap is also shown to be highly efficient. Runtime improvements of between 2.3times and 82times are obtained over existing algorithms when targeting five LUTs. Area and runtime results comparing IMap to the other mappers when targeting four and six LUTs are also presented

Design methods for OR-AND-OR three-level networks are useful for exploiting the flexibility of logic blocks in many complex programmable logic devices. This paper presents T RIMIN, a fast heuristic algorithm for designing OR-AND-OR networks from sum-of-products expressions. Each output of the network realizes a sum-of-complex-terms expression, where a complex term (CT) is similar to a product-of-sums expression. TRIMIN 's objective is to lower the number of gates in the network. It first generates a set of CTs by applying factorization techniques; then, it solves a set-covering problem by using a greedy algorithm to select a subset of the CTs. The effectiveness of TRIMIN is demonstrated through experimental results.

We present a new multivariate interpolation algorithm over arbitrary fields which is primarily suited for small finite fields. Given function values at arbitrary t points, we show that it is possible to find an n-variable interpolating polynomial with at most t terms, using the number of field operations that is polynomial in t and n. The algorithm exploits the structure of the multivariate generalized Vandermonde matrix associated with the problem. Relative to the univariate interpolation, only the minimal degree selection of terms cannot be guaranteed and several term selection heuristics are investigated toward obtaining low-degree polynomials. The algorithms were applied to obtain Reed-Muller and related transforms for incompletely specified functions.

One of the most difficult aspects of experimental reconfigurable architecture or computer-aided design (CAD) tool research is obtaining sufficiently large benchmark circuits. One approach to obtaining such circuits is to generate them stochastically. Current circuit generators construct combinational and sequential logic circuits. Many of today's devices, however, are being used to implement entire systems, and often these systems contain on-chip storage. This paper describes a circuit generator that constructs circuits containing significant amounts of memory. To ensure the circuits are realistic, we have performed a detailed structural analysis of such circuits; this analysis is also described in this paper.

Small-scale multiprocessors are becoming increasingly economical and common, whereas larger multiprocessors continue to have higher per-node costs. The NUMAchine multiprocessor project seeks to make large-scale multiprocessors more economical while maintaining high performance by exploring architectural and hardware features for low-cost, modular multiprocessors. To demonstrate our approach, we have implemented a prototype system that is scalable to 128 processors. An efficient directory-based cache coherence protocol exploits our hierarchical ring-based interconnect and supports sequential consistency. This paper documents the design choices and the resulting performance of the system using both simulation results and measurements on the prototype hardware.

As the capacities of field-programmable gate arrays (FPGAs) grow, they will be used to implement much larger circuits than ever before. These larger circuits often require significant amounts of storage. In order to address these storage requirements, FPGAs with large embedded memory arrays are now being developed by several vendors. One of the crucial components of an FPGA with on-chip memory is the routing structure between the memory arrays and logic resources. If this memory/logic interface is not flexible enough, many circuits will be unroutable, while if it is too flexible, it will be slower and consume more chip area than is necessary. In this paper, we show that an interconnect in which each memory pin can connect to between four and seven logic routing tracks is best in terms of both area and speed. We also show that by adding switches to support nets that connect multiple memory arrays, we can reduce the memory access time by up to 25% and improve the routability slightly.

This paper describes the design and implementation of the NUMAchine multiprocessor. As the market for CC-NUMA multiprocessors expands, this research project provides a timely architectural design and cost-effective prototype. The key to the successful implementation of our 48-processor prototype is the use of off-the-shelf components and programmable logic devices. Since this machine will serve as a research vehicle for parallel software development, a number of hardware features to enhance experimentation have been included in the design.

Many modern field programmable logic arrays (FPGAs) use lookup table (LUT) logic blocks which can be programmed to realize any function of a fixed number of inputs. It is possible to employ logic blocks that realize only a subset of all functions, while the rest can be obtained by permuting and negating the inputs such blocks, known as Universal Logic Modules (ULMs), have already been considered for application in FPGAs; we propose a new class of ULMs which is more useful in the FPGA environment. Methodology for systematic development of such blocks is presented, based on the BDD description of logic functions. We give an explicit construction of a three-input LUT replacement that requires only five programming bits, which is the optimum for such ULMs. A realistic size four-input LUT replacement is obtained which uses 13 programming bits.

This paper shows that the speed of FPGAs with large embedded memory arrays can be improved by adding direct programmable connections between the memories. Nets that connect to multiple memory arrays are often difficult to route, and are often part of the critical path of circuit implementations. The memory-to-memory connection structure proposed in this paper allows for the efficient implementation of these nets, resulting in a reduction in memory access time of up to 25% and a slight improvement in routability. 1 Introduction As FPGAs become larger, they will be used to implement entire systems, rather than small logic subcircuits. One of the key differences between these large systems and the smaller logic subcircuits is that the systems often contain memory. Architectural support for the efficient implementation of memory in nextgeneration FPGAs, therefore, is crucial. Several vendors offer FPGAs with architectural support for memory [1, 2, 3, 4, 5, 6, 7]. The memory resources in ...

In this paper, we identify performance trends and design relationships between the following components of the data memory hierarchy in a dynamically-scheduled processor: the register file, the lockup-free data cache, the stream buffers, and the interface between these components and the lower levels of the memory hierarchy. Similar performance was obtained from all systems having support for fewer than four in-flight misses, irrespective of the register-file size, the issue width of the processor, and the memory bandwidth. While providing support for more than four in-flight misses did increase system performance, the improvement was less than that obtained by increasing the number of registers. The addition of stream buffers to the investigated systems led to a significant performance increase, with the larger increases for systems having less in-flight-miss support, greater memory bandwidth, or more instruction issue capability. The performance of these systems was not significantly affected by the inclusion of traffic filters, dynamic-stride calculators, or the inclusion of the per-load non-unity stride-predictor and the incremental-prefetching techniques, which we introduce. However, the incremental prefetching technique reduces the bandwidth consumed by stream buffers by 50% without a significant impact on performance.

The multicluster architecture that we introduce offers a decentralized, dynamically scheduled architecture, in which the register files, dispatch queue, and functional units of the architecture are distributed across multiple clusters, and each cluster is assigned a subset of the architectural registers. The motivation for the multicluster architecture is to reduce the clock cycle time, relative to a single-cluster architecture with the same number of hardware resources, by reducing the size and complexity of components on critical timing paths. Resource partitioning, however, introduces instruction-execution overhead and may reduce the number of concurrently executing instructions. To counter these two negative by-products of partitioning, we developed a static instruction scheduling algorithm. We describe this algorithm, and using trace-driven simulations of SPEC92 benchmarks, evaluate its effectiveness. This evaluation indicates that for the configurations considered the multicluster architecture may have significant performance advantages at feature sizes below 0.35 /spl mu/m, and warrants further investigation.

In this paper, we introduce new analytical models for predicting the performance of parallel applications under various cache coherence protocol assumptions. The purpose of these models is to determine which protocols are to be used for which data blocks, and, in the case of dynamic protocols, also to determine when to change protocols. Although we focus on tightly-coupled multiprocessor systems, similar models can be derived for loosely-coupled distributed systems, such as networks of workstations. Our models are unique in that they lie between a large body of theoretical models that assume independence and a uniform distribution of memory accesses across processors, and a large body of address-trace oriented models that assume the availability of a precise characterization of interleaving behavior of memory accesses. The former are not very realistic, and the latter are not suitable for compile-time and run-time usage. In contrast, our models enable us to choose different input parameters depending on how the models will be used and depending on the needed accuracy in performance prediction. We present the models and show how the required parameters can be obtained. We assess the accuracy of our models on 15 parallel applications. For these applications, our most complete model predicts performance within a 10 percent margin when compared to a simulation of a sequentially consistent multiprocessor system. As part of this study, we also show the potential advantage of using dynamic hybrid protocols.

This paper provides a case study that shows how a demanding application stresses the capabilities of today's CAD tools, especially in the integration of products from multiple vendors.We relate our experiences in the design of a large, high-speed multiprocessor computer, using state of the art CAD tools.All logic circuitry is targeted to field-programmable devices (FPDs).This choice amplifies the difficulties associated with achieving a highspeed design, and places extra requirements on the CAD tools.Two main CAD systems are discussed in the paper: Cadence Logic Workbench (LWB) is employed for board-level design, and Altera MAX+plusII is used for implementation of logic circuits in FPDs.Each of these products is of great value for our project, but the integration of the two is less than satisfactory.The paper describes a custom procedure that we developed for integrating sub-designs realized in FPDs (via MAX+plusII) into our board-level designs in LWB.We also discuss experiences with Logic Modelling Smart Models, for simulation of FPDs and other types of chips.

No abstract available.

As the capacities of FPGAs grow, it becomes feasible to implement the memory portions of systems directly on an FPGA together with logic. We believe that such an FPGA must contain specialized architectural support in order to implement memories efficiently. The key feature of such architectural support is that it must be flexible enough to accommodate many different memory shapes (widths and depths) as well as allowing different numbers of independently-addressed memory blocks. This paper describes a family of centralized Field-Configurable Memory architectures which consist of a number of memory arrays and dedicated mapping blocks to combine these arrays. We also present a method for comparing these architectures, and use this method to examine the tradeoffs involved in choosing the array size and mapping block capabilities.

This paper considers the Reed-Muller transform for incompletely specified multiple-valued logic functions, which is obtained as the finite field polynomial representation. A new algorithm for dealing with single-variable functions is presented. It is applicable to finite fields of small sizes (two to four), which is of interest because only these fields are readily implementable with today's MVL technology. It is shown how such or any similar single-variable algorithm can be used to obtain a fast n-variable Reed-Muller transform based on this transform, a heuristic scheme is derived for dealing with incompletely specified functions. It has better computational properties than other methods and achieves the best results when applied to functions with a large number of unspecified points.>

A model for predicting relative performance in distributed shared memory systems is presented. The model is intended for use with systems that feature adaptive consistency schemes. Based on estimated read/write access patterns, the model determines the average steady-state communication costs in the system, which serve as a performance indicator. The model is applied to data items which may be either compact data objects or objects consisting of smaller data elements. It is shown that the best results are attained when protocol selection is done at the level of data elements.>

One area of particular importance is the design of an FPGA routing architecture, which houses the user-programmable switches and wires that are used to interconnect the FPGAs logic resources. Because the routing switches consume significant chip area and introduce propagation delays, the design of the routing architecture greatly influences both the area utilization and speed performance of an FPGA. FPGA routing architectures have already been studied using experimental techniques. This paper describes a stochastic model that facilitates exploration of a wide range of FPGA routing architectures using a theoretical approach. In the stochastic model an FPGA is represented as an N*N array of logic blocks separated by both horizontal and vertical routing channels, similar to a Xilinx FPGA. A circuit to be routed is represented by additional parameters that specify the total number of connections, and each connection's length and trajectory. The stochastic model gives an analytic expression for the routability of the circuit in the FPGA. Practically speaking, routability can be viewed as the likelihood that a circuit can be successfully routed in a given FPGA. The routability predictions from the model are validated by comparing them with the results of a previously published experimental study on FPGA routability.>

A cache consistency scheme is presented for a class of multiprocessors based on a hierarchy of rings. By taking advantage of the natural broadcast and ordering properties of rings, cache consistency is achieved via a simple, selective-broadcast based protocol requiring no complex hardware. Using address-trace driven simulations of the Hector shared-memory multiprocessor, it is shown that the scheme performs well.

A detailed routing algorithm, called the coarse graph expander (CGE), that has been designed specifically for field-programmable gate arrays (FPGAs) is described. The algorithm approaches this problem in a general way, allowing it to be used over a wide range of different FPGA routing architectures. It addresses the issue of scarce routing resources by considering the side effects that the routing of one connection has on another, and also has the ability to optimize the routing delays of time-critical connections. CGE has been used to obtain excellent routing results for several industrial circuits implemented in FPGAs with various routing architectures. The results show that CGE can route relatively large FPGAs in very close to the minimum number of tracks as determined by global routing, and it can successfully optimize the routing delays of time-critical connections. CGE has a linear run time over circuit size.>

A new technology mapping algorithm for lookup tablebased Field Programmable Gate Arrays (FPGA) is presented. The major innovation is a method for choosing gate-level decompositions based on bin packing. This approach is up to 28 times faster than a previous exhaustive approach. The algorithm also exploits reconvergent paths and replication of logic at fanout nodes to reduce the number of lookup tables in the circuit. The new algorithm is implemented in the Chortle-crf program. In an experimental comparison Chortle-crf requires 14 YO fewer lookup tables than Chortle [Fran90] and 10 ~o fewer lookup tables than mis-pga [Murg90a] to implement a set of benchmark networks. Chortle-crf can also implement a network as a circuit of Xilinx 3000 series Configurable Logic Blocks (CLBS). To implement the benchmark networks as circuits of CLBS Chortle-crf requires 12 70 fewer CLBS than mis-pga and 22 % fewer CLBS than XNFOPT [Xili89]. In these experiments Chortle-crf waa an average of 68 times faster than mis-pga and 30 times faster than XNFOPT. 1

A novel technology mapping algorithm that reduces the delay of combinational circuits implemented with lookup-table-based field-programmable gate arrays (FPGAs) is presented. The algorithm reduces the contribution of logic block delays to the critical path delay by reducing the number of lookup tables on the critical path. The key feature of the algorithm is the use of bin packing to determine the gate-level decomposition of every node in the network. In addition, reconvergent paths and the replication of logic at fanout nodes are exploited to further reduce the depth of the lookup table circuit. For fanout-free trees the algorithm will construct the optimal depth K-input table circuit when K is less than or equal to 6.>

A novel, hybrid protocol LAN called TORNET2 is proposed, and its performance is evaluated. TORNET2 is a ring intended for high-speed applications in the 100 Mb/s range. Short-packet, high-priority traffic is handled by the register insertion technique. Combining this protocol with the early-release token protocol for handling low-priority asynchronous traffic is the novel aspect of TORNET2. The hybrid protocol operates in such a way that high-priority packets may be embedded in low-priority packets. This results in the best possible transfer delay for the high-priority traffic. In fact, the high-priority traffic is unaffected by the presence of low-priority traffic. Low-priority traffic is not locked out by high-priority traffic, but its transfer delay performance degrades as the volume of high-priority traffic increases. An approximate performance analysis of the TORNET2 network along with simulation results to verify the analysis is presented.>

Algorithms for synthesis of four-valued one- and two-variable functions for CCD (charge coupled device) implementation are proposed. One-variable synthesis is based on the observation that the cost of a realization of a function f(x) increases in the presence of breaks, or negative transitions, in the value of f as x increases. The function is decomposed to minimize the number of such transitions. Two-variable functions are synthesized as a sum of products of literals, taking advantage of literals that are easily implemented in CCD technology. It is concluded that the proposed algorithms perform better than those published previously.>

The course graph expansion (CGE) detailed routing algorithm is presented for FPGAs (field-programmable gate arrays). The algorithm has the ability to resolve routing conflicts by considering the side-effects of one connection on another, and can be used over a wide range of FPGA interconnection architectures. CGE has been used to obtain excellent routing results for several industrial circuits with various FPGA routing architectures. The results show that CGE is able to route relatively large FPGAs in the absolute minimum number of tracks as determined by global routing, and that CGE has a linear run-time over circuit size.>

A multichannel local area network protocol is presented. It uses a token ring with partial register insertion as a control channel for a number of data channels. In addition to the control functions, the control channel is also used for transmission of data. The protocols allows performance comparable to an equivalent multiple-ring network. Its main advantage is simpler hardware requirements. The protocol is deterministic and suitable for real-time applications.>

The use of physically-based techniques for computer animation can result in realistic object motion. The price paid for physically-based motion synthesis lies in increased computation and information requirements.1 We introduce a new approach to realistic motion specification based on state-space controllers. A user specifies a motion by defining a goal in terms of a set of destination states. A state-space controller is then constructed, which provides an optimal-control solution that guides the object from an arbitrary starting configuration to a goal. Motions are optimized with respect to time and control energy. Becasue controllers are specified in terms of destination states only, it is easy to reuse the same controller to produce different motions (from different starting states), or to create a complex sequence of motions by concatenating several controllers. An implementation of state-space controllers is presented, in which realistic motions can be produced in real time. Several examples will be considered.

The cost effectiveness of using an overflow circuit for truncated difference operation and a metal line for charge replication in the charge-coupled device (CCD) realization of multivalue multithreshold (MVMT) functions is considered. It is shown that the use of these two circuits leads to improved realizations compared to those achieved by previous approaches.>

An algorithm called heuristic spanning creates parallelism by simultaneously investigating different areas of the plausible combinatorial search space. It is used to replace the high-temperature portion of simulated annealing. The low-temperature portion of simulated annealing is sped up by a technique called section annealing, in which placement is geographically divided and the pieces are assigned to separate processors. Each processor generates simulated-annealing-style moves for the cells in its area and communicates the moves to other processors as necessary. Heuristic spanning and section annealing are shown experimentally to converge to the same final cost function as regular simulated annealing. These approaches achieve significant speedup over uniprocessor simulated annealing, giving high-quality VLSI placement of standard cells in a short period of time.>

Basic multivalued building blocks constructed using CCD (charge-coupled devices) technology are presented. They are used to realize simple threshold functions. Existing techniques for decomposition of multivalued multithreshold functions into simpler subfunctions are reviewed. Usage of the CCD technology in implementation of these subfunctions is discussed. Two new decomposition techniques are proposed. Their aim is to obtain realizations that are better suited to CCD technology in terms of the maximum number of thresholds per element and the generation of negative weights. Synthesis techniques based on the proposed decompositions are presented and compared. Although 4-valued logic functions are stressed, the techniques are, in principle, applicable to functions of any radix.

This correspondence points out that the scope of application of the matrix model for MOS complex gates proposed by El-ziq and Su1does not cover general structures of this type. Also, an example is given to show that a complete detection test set for single stuck-at faults may not be able to detect all multiple faults in a fanout-free and irredundant MOS complex gate.

A tree representation of a combinational network is developed. An algorithm is proposed for finding the functional expression realized by the network. The tree representation has storage requirement linear with respect to the number of input-output paths in the network. It is shown that rmding the complementary function and generating network SPOOF can be performed efficiently on the tree structure.

Previous experience in implementing the prime factor Fourier transform (PFFT) showed that it was much more difficult to do than the FF because of its complicated structure. In most FFT implementations the "butterfly" structure is the basic arithmetic element implemented. It is much simpler than the equivalent PFFT unit.

TORNET is an experimental local area computer network presently being designed and built in the Computer Group Laboratory of the Department of Electrical Engineering at the University of Toronto. The network consists of a number of local rings, each attached to a central ring. The local rings employ a variation on the slotted-ring format that uses a limited insertion technique to achieve reasonable response times for character traffic among many devices and small computers. Two fixed-length packet formats (one byte or 128 bytes of data) are used on the local rings. Only the longer format is used on the central ring which generally provides record level access to shared specialized equipment.

This correspondence describes an application of COS/MOS integrated circuits in the design of ternary rate-multipliers. The logical implementation of two types of ternary rate-multiplier is described. The first type produces an unevenly spaced output pulse train, while in the second one the output pulses are uniformly spaced. Advantages and disadvantages of the two types are presented.

A technique for fault detection of many-valued multithreshold switching networks is presented. An arbitrary network, implemented with R-valued multithreshold gates, called MT(R), can be transformed into an MT(R + 1) or an MT(R + 2) network which uses additional truth values for fault detection purposes. The technique leads to reduced test sets, which are usually simpler to derive.

MULTIPLE-VALUED logic has been a subject of research work for many years [1], [2]. Until the late 1960's most of the reported work was of a theoretical nature, leaving little impact on the firmly established binary approaches in the design of digital systems. Then, as LSI technology proceeded to develop rapidly, it became apparent that multiple-valued logic offers not only a rich logic structure, but also a considerable potential for application in physical systems [2], [3].

Multithreshold many-valued switching primitives are introduced. Their usefulness in the construction of many-valued storage elements is demonstrated. It is shown that they can be advantageously employed in large combinational networks, such as those found in arithmetic units.

An improved method for detection of faults in completely specified synchronous sequential machines is described. The technique is algorithmic, based on the concept of embedding the given binary machine into an easily testable R-valued machine. Heuristic optimization of additional permutation inputs is shown to lead to considerable reduction in the length of the fault sequence. A bound on the sequence length is derived, which in most cases is significantly lower than those of comparable methods.

The logic cost and speed of parallel multipliers implemented in both binary and ternary logic is studied. Binary operand lengths of 8 through 32 bits and the corresponding ternary digit range of 6 through 21 are considered. For the particular design technique used, the binary versions are slightly faster where the speed criterion is in terms of the longest logic path from operands to product. Ternary designs show smaller total cost of gates and a major reduction in the number of required inputs, indicating greatly simplified wiring interconnection complexity.

A concept of functional transformation of multivalued switching functions, used to obtain simplified implementations is presented. Given some function f, a transformed function g is generated from f by permuting some or all of the truth values. Then, implementing g and performing a reverse permutation, a simpler implementation for f is obtained. A P matrix technique is given to facilitate determination of the required permutation.

A general method for ‘simple disjoint’ decomposition of multi-valued switching functions is presented. It is also shown that the effort involved in finding optimum decompositions can be substantially reduced when a particular multi-valued switching algebra is considered.

Many-valued switching systems have been of considerable academic interest, despite the apparent inability to use them in practical applications. The main drawbacks, as pointed out by a number of authors, are the difficulties associated with the implementation of the functional basic set and the lack of adequate simplification techniques.