This paper compares a new method of simulation organization, called the significant event method, with an old one, called the clock pulse method, using as examples two automobile traffic models. The significant event method is found to be more efficient than the clock pulse method at low levels of system interaction and less efficient at high levels. A simple mathematical model for the trade-off in the relative running time of the two methods is developed. The model aids in choosing between the two simulation methods for a particular experiment. It is concluded that the significant event method can be of value in the simulation of some systems when computational efficiency is of sufficient importance.
Computing Applications
Advertisement
A cost oriented algorithm for data set allocation in storage hierarchies
Data set allocation in today's multilevel storage systems is usually based on qualitative, ad hoc decisions. While it would be desirable to obtain an optimal solution to this allocation problem, it is clear that the number of parameters involved makes it intractable to straight-forward solution. In such a situation, we must find a set of assumptions which simplify the problem greatly, but which still provide a basis for considering all significant cost elements. This paper presents such a first, quantitative allocation step. It considers many of the significant detailed costs of system utilization, data storage, data staging, and data migration. Although many avenues of further improvement are available, the present algorithm seems to be usefully accurate. As such, it can aid in quantifying the problems of data set allocation, storage system configuration, and new device designs.
A heuristic problem solving design system for equipment or furniture layouts
The Designer Problem Solver (DPS) demonstrates that the computer can perform simple design tasks. In particular, it designs furniture and equipment layouts. This task was chosen because it is simple, well defined, and characteristic of many design tasks in architecture, engineering, urban planning, and natural resource management. These space planning tasks usually involve manipulating two-dimensional representations of objects to create feasible or optimal solutions for problems involving topological and metric spatial constraints. The paper describes extensive tests performed on the program.
DPS is a heuristic problem solver with a planning phase prefixed to it. It uses the planning process to give it a sense of direction, diagnostic procedures to locate difficulties, and remedial actions to recover from difficulties. It uses a convex polygon representation to accurately describe the objects and the layout. This representation allows topological and metric constraints to be tested and the design to be easily updated.
DPS has been applied to 50 problems. While it is slow and limited in scope, the ideas behind it are general. It demonstrates the need for selectivity in controlling search and the methods used to achieve it: task-specific information, planning, diagnostic procedures, remedial actions, and selective alternative generators.
Analysis and performance of inverted data base structures
The need to envision and architecture data base systems in a hierarchical level by level framework is stressed. The inverted data base (file) organization is then analyzed, considering implementation oriented aspects. The inverted directory is viewed realistically as another large data base which itself is subjected to inversion. Formulations are derived to estimate average access time (read only) and storage requirements, formalizing the interaction of data base content characteristics, logical complexity of queries, and machine timing and blocking specifications identified as having a first-order effect on performance. The formulations presented are necessary to be used in conjunction with any index selection criteria to determine the optimum set of index keys.
A syntactic algorithm for peak detection in waveforms with applications to cardiography
Peaks in a digitized waveform are detected by an algorithm incorporating piecewise linear approximation and tabular parsing techniques. Several parameters serve to identify the waveform context enabling accurate measurement of peak amplitude, duration, and shape. The algorithm is of sufficient speed to allow on-line real-time processing. An example of its application is demonstrated on an electrocardiogram.
Copying cyclic list structures in linear time using bounded workspace
A bounded workspace copying algorithm for arbitrary list structures is given. This algorithm operates in linear time and does not require tag bits. The best previous bounded workspace copying algorithms achieved n2 time without tag bits and n log n time with one tag. The only restriction on the algorithm given here is that the copy must be placed into a contiguous section of memory. The method is applicable to fixed or variable size nodes.
An intelligent analyzer and understander of English
The paper describes a working analysis and generation program for natural language, which handles paragraph length input. Its core is a system of preferential choice between deep semantic patterns, based on what we call “semantic density.” The system is contrasted:
with syntax oriented linguistic approaches, and
with theorem proving approaches to the understanding problem.
A comparison of simulation event list algorithms
Four algorithms are considered which can be used to schedule events in a general purpose discrete simulation system. Two of the algorithms are new, one is based on an end-order tree structure for event notices, and another uses an indexed linear list. The algorithms are tested with a set of typical stochastic scheduling distributions especially chosen to show the advantages and limitations of the algorithms. The end-order tree algorithm is shown to be an advantageous, immediate replacement for the algorithm in use with current simulation languages. The most promising algorithm uses the indexed list concept. It will require an adaptive routine before it can be employed in general purpose simulators, but its performance is such that further study would be fruitful.
The quadratic hash method when the table size is not a prime number
Previous work on quadratic hash methods is limited mainly to the case where the table size is a prime number. Here, certain results are derived for composite numbers. It is shown that all composite numbers containing at least the square of one of the component primes have full-period integer-coefficient quadratic hash functions.
On maintenance of the opportunity list for class-teacher timetable problems
One of the principal components of procedures for the solution of class-teacher timetable problems is that for maintenance of the opportunity list. Opportunity list maintenance methods are based on necessary conditions for the existence of a solution. A general framework for necessary conditions, together with four specific sets of necessary conditions, is given.
An algorithm for locating adjacent storage blocks in the buddy system
A simple scheme for the determination of the location of a block of storage relative to other blocks is described. This scheme is applicable to the buddy type storage allocation systems.
The synthesis of solids bounded by many faces
A technique is presented which allows a class of solid objects to be synthesized and stored using a computer. Synthesis begins with primitive solids like a cube, wedge, or cylinder. Any solid can be moved, scaled, or rotated. Solids may also be added together or subtracted. Two algorithms to perform addition are described. For practical designers, the technique has the advantage that operations are concise, readily composed, and are given in terms of easily imagined solids. Quite short sequences of operations suffice to build up complex solids bounded by many faces.
Computer networks in higher education: socio-economic-political factors
This study presents the results of a nationwide survey of computer networks in higher education conducted during 1971-73. Five major and 18 minor networks were identified. The five major networks included: the ARPA Net, the California State College network, the University of Iowa/Iowa State University network, the Michigan Educational Research Information Triad, Inc., and the Triangle Universities Computation Center network in North Carolina. In-depth studies were conducted of the latter two nets. Based on the experiences of these operating networks, a number of factors are identified for consideration in developing networks. Finally, recommendations are advanced regarding the development of networks in higher education in the future.
The Dilogarithm function of a real argument [S22]
The dilogarithm function [1-3], defined by Li2(x) = - ∫x0 (1/z) ln (1 - z) dz, (1) occurs in several different applications in physics and engineering, ranging from quantum electrodynamics, to network analysis, to the thermodynamics of ideal ferromagnets, to the structure of polymers. A new function subroutine is developed which computes the dilogarithm function of a real argument to an accuracy of a few parts in 1015. This program was designed to be included in the usual package of library subprograms relied upon by most users. It employs an alternative computational approach to a previously published algorithm [4].
The algorithm sequential access method: an alternative to index sequential
A requirement of many computer file processing systems is the ability to access data stored on a direct access storage device (DASD) both sequentially and randomly. A popular method which provides both types of access is the index sequential organization. The purpose of this study is to propose and analyze a file organization method which should be appropriate for the same type of environment as index sequential but would be more efficient at the two types of access. This proposed method is designated the Algorithm Sequential Access Method (ASAM).
Expected time bounds for selection
A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the ith smallest of n numbers is n + min(i,n-i) + o(n). A lower bound within 9 percent of the above formula is also derived.
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