Search

This paper proposes stream model execution (SME), a new architectural technique that supports the efficient utilization of single-instruction multiple-data (SIMD) engines on general-purpose processors. SME adopts lightweight streaming processing as the intermediate representation. This process uses a hardware–software co-design approach to support efficient SIMD compilation and utilization. From a hardware perspective, the micro-architecture of SIMD engines is enabled for stream support to provide the key components to address the limitations of SIMD utilization, such as data rearrangement and non-consecutive memory access. Thus, sequential code can be compiled efficiently through a two-step procedure (i.e. C code → SME C code → vectorized code) and then executed by the SME hardware. Our experimental evaluation shows that SME can outperform previous optimization techniques by an average of 58% for multimedia kernels and 26% for applications. [ABSTRACT FROM AUTHOR]

On 6 May 2009, a seminar was held at the Computer Laboratory, Cambridge to celebrate the 60th anniversary, to the day, of the first program to be run on the electronic delay storage automatic calculator (EDSAC) computer. The seminar formed part of the University of Cambridge 800th anniversary programme. This brief paper gives an introduction to the seminar together with a transcript of the closing remarks made by Sir Maurice Wilkes, then aged 95, at the end of the event. This is followed by the two papers presented at the seminar, the first, EDSAC: a programmer remembers, is by David Barron and describes what it was like to be involved in those pioneering days. The second, Inventing the User: EDSAC in Context, is by Doron Swade and locates EDSAC in the context of the history of the internal stored program. [ABSTRACT FROM AUTHOR]

This paper reviews computation in natural systems, focusing mainly on biology and citing examples of the computation that is inherent in chemistry, natural selection, gene regulatory networks, and neuronal systems. [ABSTRACT FROM PUBLISHER]

Grid-based networks (or grids for short), such as meshes and tori, have been the underlying topology for many multicomputers, and have been extensively studied in the past as a graph topology. In this paper, we investigate some topological properties of grids without boundary wrap-around (meshes) and with boundary wrap-around (tori). In particular, we study the problem of finding the number of nodes located at/within a given distance from a given node (surface area/volume) in the network and derive some expressions for computing such a number. Furthermore, we provide similar expressions that improve on previous results already reported in the literature for some special cases of grids, notably hypercubes and k-ary n-cubes. We also show some applications of the derived expressions in analytical performance modelling of some grid-based networks under uniform and hotspot traffic loads. [ABSTRACT FROM AUTHOR]

Let G(V, E) be an undirected connected graph, where each vertex v is associated with a positive cost C(v) and each edge e = (u, v) is associated with two positive weights, W(u → v) and W(v → u). We consider a new graph problem, called the edge-orientation problem (the EOP). The major issue is to assign each edge e = (u, v) an orientation, either from u to v, denoted as u → v, or from v to u, denoted as v → u, such that maxx∈V{C(x) + Σx→z W(x → z)} is minimized. This paper first shows that the EOP is NP-hard on split graphs and planar graphs. Then, a linear-time algorithm on star graphs is proposed by the prune-and-search strategy. Finally, the algorithmic result on star graphs is extended to trees and simple cactus graphs using the dynamic programming strategy. [ABSTRACT FROM AUTHOR]

A new method to generate tests for deterministic implementations of deterministic finite state machines is proposed. The method is generic, taking a wide class of testing strategies as a parameter, and able to support both transition-oriented and fault-model-driven testing. For a given specification machine, it builds a graph encoding the given strategy and then generates a test by solving on the graph a generalization of the Rural Postman Problem. Only the first phase is domain specific and therefore precisely described in the paper. The second phase is considered a responsibility of graph specialists, though we provide guidelines for solving the most commonly encountered special case. The strategy encoding produced in the first phase is such that the second phase automatically handles, in an integrated manner, the following optimization concerns: absolute avoidance of forbidden transitions, maximum avoidance of transitions which are for some reason considered undesirable, subtest choice, subtest ordering and subtest connection, possibly with overlapping. The method accepts multi-criteria transition cost functions. If both its phases are executed precisely, it generates a test optimal with respect to the adopted strategy, and a strategy for generating absolutely optimal tests is also given. For the cases where the complexity of the first phase or of the resulting graph is problematic, guidelines for systematically conducting the phase in an approximate way are provided. [ABSTRACT FROM AUTHOR]

In this paper, we propose a scheduling-based medium access control (MAC) protocol for supporting multi-class services in wireless networks. The proposed protocol is a centralized MAC protocol which applies a coordinator node (CN) to coordinate the network. Our protocol is composed of a slot-scheduling algorithm called weighted scheduling and a quality of service (QoS) enhanced admission control algorithm. The weighted scheduling algorithm is designed to efficiently utilize the network bandwidth and fairly schedule the transmission for various types of services, whereas the QoS-enhanced admission control algorithm is proposed to manage resources and guarantee the QoS requirements of services. We make mathematical analysis for the protocol parameters and compare our protocol with IEEE 802.11e EDCF and IEEE 802.11 PCF in terms of throughput and delay by conducting simulations. The experimental results show that our protocol has the best throughput and delay performance among the simulated protocols. Moreover, our protocol has much fewer collisions than IEEE 802.11e EDCF has and always keeps on excellent performance even in the high-loaded network. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring the content to a wider readership. The Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the Department of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring the content to a wider readership. The Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the Department of Mathematical and Computer Science at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring the content to a wider readership. The Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the Department of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM AUTHOR]