Search
Join ACM

Computing Applications

Advertisement

Research and Advances

An analytic model of the HASP execution task monitor

The HASP Execution Task Monitor periodically rearranges the OS/360 dispatching chain to give tasks preemptive execution priority in inverse order to that of their cpu utilization history. The effect is to keep the I/O bound tasks active and to prevent cpu bound tasks from locking out other tasks. This paper develops a simple model of the Execution Task Monitor and employs it to study the effectiveness of the monitor in improving system performance. A modified strategy for monitor control is investigated for the case of task execution in a memory heirarchy of varying speeds.
Research and Advances

Arguments for a moratorium on the construction of a community information utility

In this article the author urges a prudent and decentralized approach to the question of the design and desirability of computerized community information utilities. Before accepting the inevitability and desirability of this or any technology, we should: (1) be sure of the feasibility (internally and externally) of what is proposed; (2) project and perhaps wait for changes in complementary techniques; (3) evaluate current and projected supplementary techniques; (4) establish the existence of demand for what is proposed; (5) take steps to involve a representative group of ultimate users in systems design, and (6) carefully think through possible side effects on man and his world view. Current proposals for community information utilities are examined in this framework, and the conclusion is drawn that society is not yet in a position to justify either the construction of an information utility in a prototype community or the acceptance of a policy in favor of its widespread implementation.
Research and Advances

A comparison of list schedules for parallel processing systems

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks is studied. Cases where task execution times are deterministic and others in which execution times are random variables are analyzed. It is shown that different algorithms suggested in the literature vary significantly in execution time and that the B-schedule of Coffman and Graham is near-optimal. A dynamic programming solution for the case in which execution times are random variables is presented.
, , and
Research and Advances

A graph formulation of a school scheduling algorithm

The problem classically titled “The Examination Schedule Problem” takes various forms in the literature. Most of these formulations can be presented in the terminology of classical Network Theory. One such formulation is: Given a nondirected network, partition its nodes into a minimal number of subsets such that no two members of the same subset are connected by an arc. An obvious lower limit to this number is the size of the largest strongly connected subgraph. Kirchgassner proved that an upper limit is this size plus one. One logical extension of the previous work is the introduction of variable length examinations where W(I) is the number of periods for exam I. The object of this paper is to generalize the definition of largest strongly connected subgraph to include the weighting of nodes, to present an approximate algorithm which usually finds the largest strongly connected subgraph, and to discuss the application of this algorithm to the solution of school scheduling and exam scheduling problems.
and
Research and Advances

Computer generation of gamma random variates with non-integral shape parameters

When the shape parameter, &agr;, is integral, generating gamma random variables with a digital computer is straightforward. There is no simple method for generating gamma random variates with non-integral shape parameters. A common procedure is to approximately generate such random variables by use of the so-called probability switch method. Another procedure, which is exact, is due to Jöhnk. This paper presents a rejection method for exactly generating gamma random variables when &agr; is greater than 1. The efficiency of the rejection method is shown to be better than the efficiency of Jöhnk's method. The paper concludes that when &agr; is non-integral the following mix of procedures yields the best combination of accuracy and efficiency: (1) when &agr; is less than 1, use Jöhnk's method; (2) when 1 is less than &agr; and &agr; is less than 5, use the rejection method; (3) when &agr; is greater than 5, use the probability switch method.
Research and Advances

Self-stabilizing systems in spite of distributed control

The synchronization task between loosely coupled cyclic sequential processes (as can be distinguished in, for instance, operating systems) can be viewed as keeping the relation “the system is in a legitimate state” invariant. As a result, each individual process step that could possibly cause violation of that relation has to be preceded by a test deciding whether the process in question is allowed to proceed or has to be delayed. The resulting design is readily—and quite systematically—implemented if the different processes can be granted mutually exclusive access to a common store in which “the current system state” is recorded.
Research and Advances

A method for composing simple traditional music by computer

A method is described for composing musical rounds by computer. This method uses some music theory plus additional heuristics. Fundamental to the method is a set of productions together with sets of applicability rules and weight rules which operate on the productions deciding when and to what extent they are available for use. Several rounds generated by the computer implementation of the method are presented. Generally, the resultant music sounds mediocre to the professional although usually pleasing to the layman. It appears that full-blown music theory is not needed for rounds—all the hardware required for structural levels is not necessary for these pieces. The author has tried to address both musicians and computer scientists.
Research and Advances

Improving locality by critical working sets

A new approach to program locality improvement via restructuring is described. The method is particularly suited to those systems where primary memory is managed according to a working set strategy. It is based on the concept of critical working set, a working set which does not contain the next memory reference. The data the method operates upon are extracted from a trace of the program to be restructured. It is shown that, except in some special cases, the method is not optimum. However, the experimental results obtained by using the method to restructure an interactive text editor and the file system module of an operating system have shown its substantial superiority over the other methods proposed in the literature.
Research and Advances

A locally-organized parser for spoken input

This paper describes LPARS, a locally-organized parsing system, designed for use in a continuous speech recognizer. LPARS processes a string of phonemes which contains ambiguity and error. The system is locally-organized in the sense that it builds local parse structures from reliable word candidates recognized anywhere in an input utterance. These local structures are used as “islands of reliability” to guide the search for more highly garbledwords which might complete the utterance.
Research and Advances

Register allocation via usage counts

This paper introduces the notion of usage counts, shows how usage counts can be developed by algorithms that eliminate redundant computations, and describes how usage counts can provide the basis for register allocation. The paper compares register allocation based on usage counts to other commonly used register allocation techniques, and presents evidence which shows that the usage count technique is significantly better than these other techniques.
Research and Advances

Enumerating full-time programmers

Data from the 1970 Census and the Department of Labor's Area Wage Surveys are used to derive estimates of the number of full-time programmers employed during the years 1969 through 1973. The 1973 figure of 180,000 is considerably less than suggested in earlier reports. It is recommended that educational administrators consider whether the many courses aimed at training programmers are justified on a vocational basis.
and
Research and Advances

A note on the calculation of average working set size

Finite-length reference string of arbitrary structure are considered, and an exact expression for average working set size in terms of “corrected” interreference interval statistics is derived. An example is discussed; upper and lower bounds are obtained; and the average working set size function is shown to be efficiently obtained for a set of page sizes, in a single pass of the reference string. This work follows the developments of a paper by Denning and Schwartz, who consider infinite-length reference strings which satisfy certain statistical properties and who derive an expression relating the asymptotic average working set size to the asymptotic missing page rate function under working set replacement.
and
Research and Advances

A back-end computer for data base management

It is proposed that the data base management function be placed on a dedicated back-end computer which accepts commands (in a relatively high level language such as the CODASYL Data Base Task Group, April 1971 Report) from a host computer, accesses the data base on secondary storage, and returns results. The advantages of such a configuration are discussed. An experimental implementation, called the eXperimental Data Management System, XDMS, is described and certain conclusions about the back-end approach are drawn from this implementation.
Research and Advances

A weighted buddy method for dynamic storage allocation

An extension of the buddy method, called the weighted buddy method, for dynamic storage allocation is presented. The weighted buddy method allows block sizes of 2k and 3·2k, whereas the original buddy method allowed only block sizes of 2k. This extension is achieved at an additional cost of only two bits per block. Simulation results are presented which compare this method with the buddy method. These results indicate that, for a uniform request distribution, the buddy system has less total memory fragmentation than the weighted buddy algorithm. However, the total fragmentation is smaller for the weighted buddy method when the requests are for exponentially distributed block sizes.
and
Research and Advances

Monitors: an operating system structuring concept

This paper develops Brinch-Hansen's concept of a monitor as a method of structuring an operating system. It introduces a form of synchronization, describes a possible method of implementation in terms of semaphores and gives a suitable proof rule. Illustrative examples include a single resource scheduler, a bounded buffer, an alarm clock, a buffer pool, a disk head optimizer, and a version of the problem of readers and writers.
Research and Advances

Structured data structures

Programming systems which permit arbitrary linked list structures enable the user to create complicated structures without sufficient protection. Deletions can result in unreachable data elements, and there is no guarantee that additions will be performed properly. To remedy this situation, this paper proposes a Data Structure Description and Manipulation Language which provides for the creation of a restricted class of data structures but ensures the correctness of the program. This is accomplished by an explicit structure declaration facility, a restriction on the permissible operations, and execution-time checks.
and

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More