Search

Presents several letters to the editor about the Association for Computing Machinery (ACM). Debate over the core competencies of the ACM; Views on computer education in the developing countries; Concern over the publication delay in the journal "Communications of the ACM."

Redundant and hybrid-redundant number representations are used extensively to speed up arithmetic operations within general-purpose and special-purpose digital systems, with the latter (containing both redundant and nonredundant digits) offering cost advantages over fully redundant systems. We use weighted bit-set (WBS) encoding as a paradigm for uniform treatment of five previously studied variants of hybrid-redundant systems. We then extend the class of hybrid-redundant numbers to coincide with the entire set of canonical WBS numbers by allowing an arbitrary nonredundant position, heretofore restricted to ordinary bits (posibits), to hold a negatively weighted bit (negabit). This flexibility leads to interesting and useful symmetric variants of hybrid-redundant representations. We provide a high-level circuit design, based solely on binary full-adders, for a constant-time universal hybrid-redundant adder capable of producing a canonical WBS-encoded sum of two canonical WBS (or extended hybrid) numbers. This is made possible by the use of conventional binary full-adders for reducing any collection of three posibits and negabits, where negabits use an inverted encoding. We compare our adder to previous designs, showing advantages in speed, cost, and regularity. Furthermore we explore representationally closed addition schemes, holding the benefit of greater regularity and reusability, and provide high-level representationally closed designs for all the previously studied variants of hybrid redundancy and for the new symmetric variants introduced here. Finally, we present a new functionality for a conventional (4; 2) compressor in combining any collection of five equally weighted negabits and posibits, and show its utility in the design of multipliers for extended hybrid-redundant numbers.

We introduce the notion of two-valued digit (twit) as a binary variable that can assume one of two different integer values. Posibits, or simply bits, in {O, 1} and negabits in {-1, 0}, commonly used in two's-complement representations and (n, p) encoding of binary signed digits, are special cases of twits. A weighted bit-set (WBS) encoding, which generalizes the two's-complement encoding by allowing one or more posibits and/or negabits in each radix-2 position, has been shown to unify many efficient implementations of redundant number systems. A collection of equally weighted twits, including ones with non- contiguous values (e.g., {-1, 1} or {O, 2}), can lead to wider representation range without the added storage and interconnection costs associated with multivalued digit sets. We present weighted twit-set (WTS) encodings as a generalization of WBS encodings, examine key properties of this new class of encodings, and show that any redundant number system (e.g., generalized signed-digit and hybrid-redundant systems), including those that are based on noncontiguous and/or zero-excluded digit sets, Is faithfully representable by WTS. encoding. We highlight this broad coverage by a tree chart having WTS representations at its root and various useful redundant representations at its many internal nodes and leaves. We further examine how highly optimized conventional components such as standard full/half-adders and compressors may be used for arithmetic on WTS-encoded operands, thus allowing highly efficient and VLSI-friendly circuit implementations. For example, focusing on the WBS-like subclass of WTS encodings, we describe a twit-based implementation of a particular stored-transfer representation which offers area and speed advantages over other similar designs based on WBS and hybrid-redundant representations. [ABSTRACT FROM AUTHOR]

Current and future requirements for adaptive real-time image compression challenge even the capabilities of highly parallel realizations in terms of hardware performance. Previously proposed linear array structures for full-search vector quantization do not offer scalability and adaptivity in this context, because they require separate data/control pins for dynamically updating the codevectors and complicated interlock mechanisms to ensure that the regular data flow is not corrupted as a result of updates. We explore the design space for full-search vector quantizers and propose a novel linear processor array architecture in which global wiring is limited to clock and power supply distribution, thus allowing high-speed processing in spite of only limited communication with the host via the boundary processors. The resulting fully pipelined design is not only area-efficient for VLSI implementation but is also readily scalable and offers extremely high performance.

Previous designs of programmable FIR digital filters have demonstrated that the use of broadcast data and control can lead to a high performance-to-cost ratio. As the technology advances to the deep sub-micrometer regime, such an approach should be re-examined by taking the effect of interconnections into account. In this paper, we show that the contribution of interconnect delay to the cycle time is no longer negligible and will hamper the scalability of such broadcast designs. Further speed and density improvements through scaling can be secured by the fully pipelined design in which both data and control signals are restricted to local connections.

For a large numberNof data points, linear FFT arrays consisting of Θ(log2N) processors provide significant economy in hardware. In this paper we discuss the radix-2 decimation-in-frequency Cooley-Tukey algorithm implemented on linear arrays, thereby allowing a continuous real-time application using a word-serial input data stream to the linear arrays. In order to avoid memory access and data path switching under central control, we present a novel data-driven scheme permitting the proposed linear arrays to correctly operate on arbitrarily arriving signal sequences. This distributed control scheme incorporates a control signal propagated with the data signals, in the form of a tag attached to data items. The tag provides control information to initiate the access to the memory containing the coefficients and to select and appropriate data path so that regular data flow can be achieved within the linear array. The cascade structures are well suited for the computation and can operate in pipeline fashion at extremely high data rates. The proposed data-driven control scheme can be used with both synchronous and asynchronous (wavefront) processor arrays.

URISC is a single-instruction universal computer which appears to be ideal for introducing basic computer organization concepts to novice students. In this paper, the specifications of URISC are given and complete implementations of its control unit are presented. The authors' experiences with the use of URISC in the classroom environment are discussed briefly.

It is well known that any n-variable logic function can be realized by a multiplexer (selector) with no additional external logic. Thus multiplexers have come to be known as universal logic modules. This approach to logic function realization requires the use of a 2n-input multiplexer with constant data inputs, or a 2n−1-input multiplexer whose data inputs are constants and single-variable functions; that is, each input is 0, 1, x or x′ for some variable x. This paper deals with conditions and algorithms for realizing some logic functions using smaller multiplexers. More precisely, a computationally simple condition is formulated to determine whether a given n-variable logic function is realizable by a multiplexer having 2n−2 or fewer inputs, and an algorithm is presented for finding the smallest subset of variables, containing n − 2 or fewer members, to be used as control inputs in a minimal multiplexer realization. Once the control inputs are known, the data input functions can be readily computed.

A letter to the editor is presented in response to the article "Are the Costs of 'Free' Too High in Online Education?" by Michael A. Cusumano in the April 2013 issue.

To alleviate the computational burden of previous virtual network embedding (VNE) approaches when the resource network scales up significantly, we propose an efficient node ranking strategy that considers both global and local topological characteristics of the substrate network in mapping virtual nodes to physical nodes. This method ranks the substrate network nodes in two stages. First, all nodes are ranked globally with respect to the stationary distribution of the entire network. Then, a connected subset of the ranked substrate nodes, forming the H‐admissible embedding subgraph, is extracted. Finally, the subgraph nodes are ranked according to a local node ranking vector derived from a random‐walking scheme. The local rank vector is resolved using discrete Green's function satisfying the Dirichelet boundary condition. The more accurate association of node demands and resources that our proposed method provides leads to both better acceptance ratio and lower computational overhead. These claims have been justified via theoretical and algorithmic presentation of our scheme and offer experimental results obtained through simulation, to confirm its execution efficiency and solution quality compared with a couple of previous VNE proposals. This paper proposes an efficient node ranking strategy that considers both global and local topological characteristics of the substrate network in mapping virtual nodes to physical nodes. This method ranks the substrate network nodes globally at first. Then, extracts a connected subset of the ranked substrate nodes forming the H‐admissible embedding subgraph, and the subgraph nodes are ranked according to a local node ranking vector derived from a random‐walking scheme.