This paper describes a technique for achieving supervector performance on a CRAY-1 in a purely FORTRAN environment {i.e., without resorting to assembler language).The technique can be applied to a wide variety of algorithms m hnear algebra, and is beneficial m other architectural settings.

AnSTRACT Let G and G* be programs represented by directed graphs There is defined a relation ~-s.r between G and G* that formahzes the notton of G* simulating G with Sffold loss of space efficiency and T-fold loss of time efficiency, ~t is proved that ff G - lo B n + O(Iog2 logz n) KEY WORDS AND PHRASES ancestor tree, complexity, control structure, dtrected graph, embedding CR CATEGORIES 4 22, 4 34, 5 24, 5 32 IntroducttonIn a previous paper [1] we made precise some intuitwe observations concerning the efficiency of structured programs by defining a combinatorial relation that corresponds to the notion of uniform szrnulatton between programs.Informally, we say that a program G* uniformly simulates a program G ff G* carries out the computation of G (and possibly addRlonal computation which might be regarded as "bookkeeping") in such a way that the space-time efficiency of G is degraded by a factor that is independent of the size of G.The main results of [ 1] indicate that the nonexistence of uniform simulations among many well-known classes of control structures is at least in part due to the combinatorial aspects of program structure and not to such details of program orgamzation as choice of data structures or limitations on the form of Boolean expressions.Indeed, the main result of [1, Th. 5.1] provides a nontrivml lower bound on the loss of space-time efficiency in any structured simulation of a goto program.This short note extends that result, improving the space-time inequality of [1, Th. 5.1] by an exponentml.Thus we now show that there are goto programs with n statements such that for any structured simulation either Pernnsslon to copy wtthout fee all or part of this matenal is granted provided that the copies are not made or distnbuted for direct commercial advantage, the ACM copyright notice and the tttle of the pubhcation and Rs date appear, and notice is gwen that copying ts by permission of the AssoclaUon for Computing Machinery To copy otherwise, or to republish, requires a fee and/or specific permission These results were announced at the 1976 Johns Hopkins Conference on Information Sciences and Systems

Control structures and data structures are modeled by directed graphs. In the control case nodes represent executable statements and arcs represent possible flow of control; in the data case nodes represent memory locations and arcs represent logical adjacencies in the data structure. Classes of graphs are compared by a relation ≤ S.T where G ≤ S.T H if G can be embedded in H with at most a T -fold increase in distance between embedded nodes by making at most S “copies” of any node in G . For both control structures and data structures, S and T are interpreted as space and time constants, respectively. Results are presented that establish hierarchies with respect to ≤ S.T for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures.

The running time or computational complexity of a sequential process is usually determined by summing weights attached to the basic operations from which the process is derived. In practice, however, the complexity is often limited by how efficiently it can access its data structures and how efficiently it can control program flow. Furthermore, it has been extensively argued [4] that certain limitations on the process sequencing mechanisms available to the programmer result in more “efficient” representations for the underlying processes. In this paper we will examine these issues in an attempt to assess the “power” of various data and control structures.