December 1981 - Vol. 24 No. 12
Features
A generalized user interface for applications programs
A general method for using disk files (instead of a more conventional parameter-passing mechanism) to transfer control information from a user interface to a set of related applications programs is described. This technique effectively moves much of the user interface, including command decoding and limited parameter checking, from the applications programs to a table-driven executive.
Analysis of future event set algorithms for discrete event simulation
New analytical and empirical results for the performance of future event set algorithms in discrete event simulation are presented. These results provide a clear insight to the factors affecting algorithm performance, permit evaluation of the hold model, and determine the best algorithm(s) to use. The analytical results include a classification of distributions for efficient insertion scanning of a linear structure. In addition, it is shown that when more than one distribution is present, there is generally an increase in the probability that new insertions will have smaller times than those in the future event set. Twelve algorithms, including most of those recently proposed, were empirically evaluated using primarily simulation models. Of the twelve tested, four performed well, three performed fairly, and five performed poorly.
An algorithm for exhaustive generation of building floor plans
The combinatorial complexity of most floor plan design problems makes it practically impossible to obtain a systematic knowledge of possible solutions using pencil and paper. The objective of this paper is to contribute to the development of computer methods providing such knowledge for the designer. The paper describes an algorithm which generates all possible rectangular plans on modular grids with congruent cells, subject to constraints on total area, room areas, wall lengths, room adjacencies, and room orientations. To make room sizes regular and limit the solution set only such grids are used which minimize the number of cells in the smallest room. The description is sufficiently detailed to serve as a basis for programming. Test results for a Pascal implementation of the algorithm are reported. Realistic problems of up to ten rooms have been solved in modest lengths of computer time. The results indicate that the approach of exhaustive generation may prove to be more fruitful than generally assumed.
A two-list synchronization procedure for discrete event simulation
The traditional mechanism for maintaining a list of pending events in a discrete event simulation is the simple linked list. However, in large scale simulations this list often becomes cumbersome to maintain since the number of pending events may become quite large. As a result, the execution time required by the simple linked list is often a significant portion of total simulation time. Several papers have been published suggesting improved synchronization procedures. The most efficient procedures reported are the time-indexed procedure and the two-level procedure. Both methodologies are much more efficient than simple linked lists; however, neither has been adopted by a general purpose simulation language. Further, both procedures require external parameter definition, which is a major handicap to their adoption by a general purpose language. This paper introduces a new sychronization procedure, the two-list procedure, which is much faster than simple linked lists for large pending event files. This procedure was designed for implementation in Fortran, and properly implemented it is transparent to the user. Thus it is ideal for adoption by general purpose simulation languages.
Reciprocal hashing: a method for generating minimal perfect hashing functions
A method is presented for building minimal perfect hash functions, i.e., functions which allow single probe retrieval from minimally sized tables of identifier sets. A proof of existence for minimal perfect hash functions of a special type (reciprocal type) is given. Two algorithms for determining hash functions of reciprocal type are presented and their practical limitations are discussed. Further, some application results are given and compared with those of earlier approaches for perfect hashing.
