January 1985 - Vol. 28 No. 1
Features
Reduced instruction set computers
Reduced instruction set computers aim for both simplicity in hardware and synergy between architectures and compilers. Optimizing compilers are used to compile programming languages down to instructions that are as unencumbered as microinstructions in a large virtual address space, and to make the instruction cycle time as fast as possible.
Sixty-four small computers are connected by a network of point-to-point communication channels in the plan of a binary 6-cube. This “Cosmic Cube” computer is a hardware simulation of a future VLSI implementation that will consist of single-chip nodes. The machine offers high degrees of concurrency in applications and suggests that future machines with thousands of nodes are both feasible and attractive.
The Manchester prototype dataflow computer
The Manchester project has developed a powerful dataflow processor based on dynamic tagging. This processor is large enough to tackle realistic applications and exhibits impressive speedup for programs with sufficient parallelism.
This is the third report prepared by the ACM Committee on Scientific Freedom and Human Rights (CSFHR). The first was published in the March 1981 Communications and the second in the December 1982 issue. This report is an update. Since the committee intends to publish future updates, it would appreciate receiving further information about computer scientists whose rights have been violated. Such information should be sent to: Jack Minker, Vice-Chairman, Committee on Scientific Freedom and Human Rights, Department of Computer Science, University of Maryland, College Park, MD 29742.Because those whose scientific freedom or human rights have been violated derive sustenance and support from contacts with their colleagues, the CSFHR has established a program in which ACM chapters “adopt” individual scientists and correspond with them. Such correspondence should touch on the personal and scientific and not discuss political matters. These letters greatly improve the morale of the recipients and are one of the few ways they can keep current with computer science and technology. This CSFHR program is directed by Helen Takacs (P.O. Drawer CS, Mississippi State, MS 39762).
A style analysis of C programs
A large quantity of well-respected software is tested against a series of metrics designed to measure program lucidity, with intriguing results. Although slanted toward software written in the C language, the measures are adaptable for analyzing most high-level languages.
Design and implementation of a very small linear algebra program package
Microcomputers, when properly programmed, have sufficient memory and speed to successfully perform serious calculations of modest size--linear equations, least squares, matrix inverse or generalized inverse, and the symmetric matrix eigenproblem.
An inverted taxonomy of sorting algorithms
An alternative taxonomy (to that of Knuth and others) of sorting algorithms is proposed. It emerges naturally out of a top-down approach to the derivation of sorting algorithms. Work done in automatic program synthesis has produced interesting results about sorting algorithms that suggest this approach. In particular, all sorts are divided into two categories: hardsplit/easyjoin and easysplit/hardjoin. Quicksort and merge sort, respectively, are the canonical examples in these categories. Insertion sort and selection sort are seen to be instances of merge sort and quicksort, respectively, and sinking sort and bubble sort are in-place versions of insertion sort and selection sort. Such an organization introduces new insights into the connections and symmetries among sorting algorithms, and is based on a higher level, more abstract, and conceptually simple basis. It is proposed as an alternative way of understanding, describing, and teaching sorting algorithms.
