Correction to `Allocating programs containing branches and loopswithin a multiple processor system'

A number of typographical errors in the above-mentioned paper (see ibid., vol.12, no.10, p.1018-24 (1986)) are corrected     

Comments on `A necessary and sufficient condition for stability ofa perturbed system' by Q. Huang and R. Liu

It is pointed out that for a given controller, the sets of additive, multiplicative, and stable-factor perturbations that the plant can have without destabilizing the control system can be completely parametrized by using D.C. Youla's parametrization and by noting that the roles that the plant and the controller play in a standard feedback control configuration can be reversed     

Computing network flow on a multiple processor pipeline

We demonstrate the feasibility of a distributed implementation of the Goldberg-Tarjan algorithm for finding the maximum flow in a network. Unlike other parallel implementations of this algorithm, where the network graph is partitioned among many processors, we partition the algorithm among processors arranged in a pipeline. The network graph data are distributed among the processors according to local requirements. The partitioned algorithm is implemented on six processors within a 15-processor pipelined message-passing multicomputer operating at 5 MHz. We used randomly generated networks with integer capacities as examples. Performance estimates based upon a six-processor pipelined implementation indicated a speedup between 3.8 and 5.9 over a single processor     

Implementing sequentially consistent programs on processor consistent platforms

Designers of distributed algorithms typically assume strong memory consistency guarantees, but system implementations provide weaker guarantees for better performance and scalability. This motivates the study of how to implement programs designed for sequential consistency on platforms with weaker consistency models. Typically, such implementations are impossible using only read and write operations to shared variables. One variant of processor consistency originally proposed by Goodman and called here PC-G is an exception because it provides just enough consistency to implement mutual exclusion using only reads and writes. This paper investigates the existence of compilers to convert arbitrary programs that use shared read/write variables with sequentially consistent memory semantics, to programs that use read/write variables with PC-G consistency semantics. We first provide a simple program transformation, and prove that it correctly compiles any 2-process program to a PC-G memory system, while preserving wait-freedom. We next prove that even a substantial generalization of this transformation cannot be a compiler for even a very restricted class of 3-process programs. Even though our program transformation is not a general compiler for three or more processes, it does correctly transform some specific n-process programs. In particular, for the special case of the (necessarily randomized) Test&Set algorithm of Tromp and Vitanyi, our transformation extends to any number of processes, thus providing the first algorithm for expected wait-free Test&Set on any weak memory system, using only read/write variables.     

Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach

We consider the multiprocessor scheduling of unit time tasks with precedence constraints and finite set of limited resources. Each task demands some amount of resources for its execution and the total demand for each kind of resources must not exceed a certain limit at any instant of time. Our objective is to find out the minimum time schedule which satisfies the partial orders and the resource usage constraints. We have applied Genetic Algorithm for the present problem. We have shown that the Genetic Algorithm is quite superior to the First Fit Decreasing method.     

Comments. with reply, on `Tip of the flowchart iceberg' by D.A.Scanlan

The commenters maintain that the study in the above article (see ibid., vol.6, no.5, p.28-36 (1990)) reveals only the tip of a massive iceberg because the author restricts his attention to flowcharts. They report that their experience in developing and using graphical representations based on valuation contexts suggests that when graphical methods are fully appreciated and used, they will radically change the way we think about systems and the way we practice software development. They disagree with the claim that some of Scanlan's examples are unrealistically complex. The author thanks the commenters for their favorable and insightful comments about the importance of graphics to depict complex systems. He maintains his position that the most complex algorithm in the experiment was unrealistically complex     

The implementation of a 3D Navier-Stokes algorithm on an algorithm oriented processor

The multiprocessor system ATOMS has been used to solve 3D Navier-Stokes problems. ATOMS was originally designed at AT&T Bell Laboratories for Molecular Dynamics calculations. However, certain hardware features were included in the design to permit data transfer between processor boards as closely coupled linear array of processors. In this mode we refer to the multiprocessor system as DNSP (AT&T's/Delft Navier-Stokes Processor).

An algorithm for calculating the buoyancy-driven laminar/turbulent flow in a 3D cavity has been implemented on the DNSP. For this algorithm an efficiency of 35% (which amounts to 14 Mflops) is obtained. This high efficiency can be reached thanks to the strong coupling between the algorithm and the architecture of the multiprocessor system. The speed is obtained at very low cost, resulting in a cost/performance ratio for the DNSP which is at least an order of magnitude lower than (mini-)supercomputers.     

High-performance processor design based on 3D on-chip cache

Interconnection becomes one of main concerns in current and future microprocessor designs from both performance and consumption. Three-dimensional integration technology, with its capability to shorten the wire length, is a promising method to mitigate the interconnection related issues. In this paper we implement a novel high-performance processor architecture based 3D on-chip cache to show the potential performance and power benefits achievable through 3D integration technology. We separate other logic module and cache module and stack 3D cache with the processor which reduces the global interconnection, power consumption and improves access speed. The performance of 3D processor and 3D cache at different node is simulated using 3D Cacti tools and theoretical algorithms. The results show that comparing with 2D, power consumption of the storage system is reduced by about 50%, access time and cycle time of the processor increase 18.57% and 21.41%, respectively. The reduced percentage of the critical path delay is up to 81.17%.     

Comments, with reply, on `On criteria for module interfaces' by D.Hoffman

The commenter acknowledges that the practical criteria provided in the above-titled paper (see ibid., vol.16, no.5, p.537-42, 1990), offer substantive guidelines for designing module interfaces. He points out that the results obtained can be further improved and certain remaining conflicts resolved through consideration of established principles of structured design and software engineering. He illustrates his point with an example involving the specification of a stack interface that requires two or three separate references to replace one. He presents two designs and argues that the first is better. The author refutes the commenter's arguments and argues that the second design is better     

Computing programs containing band linear recurrences on vectorsupercomputers

Many large-scale scientific and engineering computations, e.g., some of the Grand Challenge problems, spend a major portion of execution time in their core loops computing band linear recurrences (BLRs). Conventional compiler parallelization techniques cannot generate scalable parallel code for this type of computation because they respect loop-carried dependences (LCDs) in programs, and there is a limited amount of parallelism in a BLR with respect to LCDs. For many applications, using library routines to replace the core BLR requires the separation of BLR from its dependent computation, which usually incurs significant overhead. In this paper, we present a new scalable algorithm called the Regular Schedule, for parallel evaluation of BLRs. We describe our implementation of the Regular Schedule and discuss how to obtain maximum memory throughput in implementing the schedule on vector supercomputers. We also illustrate our approach, based on our Regular Schedule, to parallelizing programs containing BLR and other kinds of code. Significant improvements in CPU performance for a range of programs containing BLR implemented using the Regular Schedule in C over the same programs implemented using highly optimized coded-in-assembly BLAS routines [11] are demonstrated on Convex C240. Our approach can be used both at the user level in parallel programming code containing BLRs, and in compiler parallelization of such programs combined with recurrence recognition techniques for vector supercomputers     

Comments on a paper by Kidd

The problem of speed control of a DC drive system with a variable moment-of-inertia load has recently been considered for the purpose of comparison of the performance of a non-linear adaptive control system and a classical linear control system. The results of this comparison apparently show that the performance of the adaptive controller is inferior to that of the linear control configuration under non-ideal conditions. This paper uses the same example to show that a simple adaptive controller can easily overcome the difficulties of this test.     

Comments on a paper by neuhold and studer

The authors of [5] described their experience in applying Hoare's method of program verification to an existing program. They reported two difficulties. The first was that certain Boolean expressions occurring in conditional or while statements needed to be strengthened to enable verification. This claim is false, and their three putative examples are refuted. The second difficulty was that the program had to be modified to use very restricted forms of jumps and procedures. Re this, we document recent work which enables these restrictions to be lifted.     

Synthesis of halftone 3D images on an array processor

A fast generation of shaded images of CSG-defined objects could be accomplished by employing a general-purpose array processor. To fully exploit the computing power of such a machine, the visualization algorithm should be tailored to that specific kind of architecture. A parallel adaptation of the ray-tracing method and algorithm kernel operations is introduced. The performance analysis shows suitability of the approach for interactive CAD applications. Test pictures are presented.     

Comments, with reply, on 'Structured flowcharts outperform pseudocode: an experimental comparison' by D.A. Scanlan

The commenter maintains that what is being compared in the abovementioned article (see ibid., vol.6, no.5, p.28-36 (1989)) is the relative stability of flowcharts and pseudocode for the expression of a restricted aspect of actual programs, better isolated in the lab than in practice. He notes that the author avoids any loops in his three test algorithms. He points out that flowcharts require special output capabilities and an elaborate editor if they are to compare as a tool with pseudocode. The author responds that the commenter's point about the lack of loops in the algorithms is well taken but that he chose algorithms very similar to those used in a study with which he wished to compare his results. He addresses other points made by the commenter, defending his own approach and conclusions.<>     

基于Nios的温备份智能容错系统的设计

本文是在充分研究了智能故障诊断、容错控制以及可靠性理论的前提下,运用FPGA、Nios处理器、控制理论、人工智能等相关知识,提出了一个能在实际的网络系统中提高服务器运行可靠性的有效方法——温备份智能容错系统。该方法使用Nios软核处理器以及FPGA的优点,运用SOPC Builder工具设计了一个智能仲裁器的核心部件。该仲裁器能够智能地获取服务器的状态、同步服务器的内容以及控制服务器的开启和关闭。从而提高了系统的可靠性,延长了服务器的使用寿命。本文给出了该方法的实现模型及详细实现步骤。     

Comments on `Adaptive manipulator control: a case study' by J.Slotine and W. Li

The commenter establishes the stability in the sense of Lyapunov of the adaptive motion controller for robot manipulators reported by J. Slotine and W. Li (ibid., vol.33, p.995-1003, Nov. 1988)