Security and Privacy
Advertisement
Information science in a Ph.D. computer science program
This report contains recommendations on a sample course curriculum in the general area of information organization and information system design in a Ph.D. Computer Science Program. The subject area is first briefly described, followed by a listing of some desirable graduate-level courses. Suitable bibliographies are appended.
Coding the Lehmer pseudo-random number generator
An algorithm and coding technique is presented for quick evaluation of the Lehmer pseudo-random number generator modulo 2 ** 31 - 1, a prime Mersenne number which produces 2 ** 31 - 2 numbers, on a p-bit (greater than 31) computer. The computation method is extendible to limited problems in modular arithmetic. Prime factorization for 2 ** 61 - 2 and a primitive root for 2 ** 61 - 1, the next largest prime Mersenne number, are given for possible construction of a pseudo-random number generator of increased cycle length.
Extremely portable random number generator
Extremely portable subroutines are sometimes needed for which moderate quality and efficiency suffice. Typically, this occurs for library functions (like random number generation and incore sorting) which are not entirely universal or are not used in a standardized way.
The literature on random number generators does not seem to contain an algorithm that meets requirements of this sort. An extremely portable 8-line FORTRAN program is provided which is based on an important paper by Coveyou and MacPherson (1967). Using their methods, Fourier analysis is applied to the probability function for the consecutive n-tuples provided by our generator (with n less than or equal to 4). While the small modulus which must be used to maintain portability prevents the quality of the generator from being high, the generator compares well with the bounds established in the above mentioned paper.
Exclusive simulation of activity in digital networks
A technique for simulating the detailed logic networks of large and active digital systems is described. Essential objectives sought are improved ease and economy in model generation, economy in execution time and space, and a facility for handling simultaneous activities. The main results obtained are a clear and useful separation of structural and behavioral model description, a reduction of manual tasks in converting Boolean logic into a structural model, the elimination of manual processes in achieving exclusive simulation of activity, an event-scheduling technique which does not deteriorate in economy as the event queue grows in length, and a simulation procedure which deals effectively with any mixture of serial and simultaneous activities. The passage of time is simulated in a precise, quantitative fashion, and systems to be simulated may be combinations of synchronous and asynchronous logic. Certain aspects of the techniques described may be used for the simulation of network structures other than digital networks.
Some criteria for time-sharing system performance
Time-sharing systems, as defined in this article, are those multiaccess systems which permit a terminal user to utilize essentially the full resources of the system while sharing its time with other terminal users. It is each terminal user's ability to utilize the full resources of the system that makes quantitative evaluation of time-sharing systems particularly difficult. Six criteria are described which have been successfully used to perform first-level quantitative time-sharing system performance evaluation.
Directed random generation of sentences
The problem of producing sentences of a transformational grammar by using a random generator to create phrase structure trees for input to the lexical insertion and transformational phases is discussed. A purely random generator will produce base trees which will be blocked by the transformations, and which are frequently too long to be of practical interest. A solution is offered in the form of a computer program which allows the user to constrain and direct the generation by the simple but powerful device of restricted subtrees. The program is a directed random generator which accepts as input a subtree with restrictions and produces around it a tree which satisfies the restrictions and is ready for the next phase of the grammar. The underlying linguistic model is that of Noam Chomsky, as presented in Aspects of the Theory of Syntax. The program is written in FORTRAN IV for the IBM 360/67 and is part of a unified computer system for transformational grammar. It is currently being used with several partial grammars of English.
Methods of analyzing the control flow and data flow of programs during compilation are applied to transforming the program to improve object time efficiency. Dominance relationships, indicating which statements are necessarily executed before others, are used to do global common expression elimination and loop identification. Implementation of these and other optimizations in OS/360 FORTRAN H are described.
The role of programming in a Ph.D. computer science program
In this general paper the role of programming in advanced graduate training is discussed. Subject matter related to programming as well as programming per se is considered. The importance and application of formalism are considered and also the need for good empirical experimentation. A brief outline for a sequence of courses is included, and subject headings that have been obtained from an extensive bibliography are given. A bibliography of programming references is included.
A system organization for resource allocation
This paper introduces a system for resource management using the concepts of “process,” “facility,” and “event.” Except for the processor no attempt has been made to give serious suggestions for the policy to be followed for resource allocation. However, a basic framework is provided in which a system analyst can express solutions to resource management problems.
The paper is divided into a tutorial presentation, a description of the system primitives, and a small collection of examples of the use of the primitives.
A SIMSCRIPT-FORTRAN case study
Two programs for a vehicle dispatching model, one written in 7040 SIMSCRIPT and the other in 7040 FORTRAN IV are compared. The comparison is made in terms of basic program design decisions, storage requirements, computer time used, and the ease of making changes.
In the SIMSCRIPT program, the primary design considerations center around the choice of model variables, model changing events, and model testing. In the FORTRAN program, basic design problems relate to the representation of the passage of time, the allocation of storage, and the organization of input data.
The comparison of these differently designed programs shows that the SIMSCRIPT program uses more computer storage and more computer time, but requires fewer program changes to introduce model revisions.
The ALCOR Illinois 7090/7094 post mortem dump
A dump technique for programs written in ALGOL 60 is described. This technique provides an intelligible analysis of an unsuccessful computation process in terms of the original source program.
GEORGE 3—A general purpose time sharing and operating system
An Operating System is described which will run on a wide variety of configurations of the I.C.T. 1900, and can handle a large number of online console users while at the same time running several offline (background) jobs. The system is not oriented towards either mode and can be either a batch processing system (such as the ATLAS Supervisor, IBSYS, or GECOS), or a multiaccess system (resembling, to the user, CTSS or MULTICS), or both simultaneously, depending on the installation, which can adjust the Schedulers.
Both online users and offline jobs use a common Command Language. The system includes a Multilevel device-independent File Store.
An experimental model of system/360
The problem of predicting the performance of modern computer systems is formidable. One general technique which can ease this problem is macroscopic simulation. This paper reports on the applicability of that technique to System/360.
The paper describes an experimental model of System/360—its hardware, software, and its environment. The measures of system performance produced by the model consist of statistics relating to turnaround time, throughput, hardware utilization, software utilization, and queueing processes.
The model is mechanized in SIMSCRIPT and consists of some 1750 statements. An auxiliary program, the Job Generator, creates automatically the properties of System/360 jobs that get simulated.
The “information explosion” noted in recent years makes it essential that storage requirements for all information be kept to a minimum. A fully automatic and rapid three-part compressor which can be used with “any” body of information to greatly reduce slow external storage requirements and to increase the rate of information transmission through a computer is described in this paper. The system will also automatically decode the compressed information on an item-by-item basis when it is required.
The three component compressors, which can be used separately to accomplish their specific tasks, are discussed: NUPAK for the automatic compression of numerical data, ANPAK for the automatic compression of “any” information, and IOPAK for further compression of information to be stored on tape or cards.
Methods for analyzing data from computer simulation experiments
This paper addresses itself to the problem of analyzing data generated by computer simulations of economic systems. We first turn to a hypothetical firm, whose operation is represented by a single-channel, multistation queueing model. The firm seeks to maximize total expected profit for the coming period by selecting one of five operating plans, where each plan incorporates a certain marketing strategy, an allocation of productive inputs, and a total cost.
The results of the simulated activity under each plan are subjected to an F-test, two multiple comparison methods, and a multiple ranking method. We illustrate, compare, and evaluate these techniques. The paper adopts the position that the particular technique of analysis (possibly not any one of the above) chosen by the experimenter should be an expression of his experimental objective: The F-test tests the homogeneity of the plans; multiple comparison methods quantify their differences; and multiple ranking methods directly identify the one best plan or best plans.
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 InvolvedCommunications 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