bluuebunny/crossref_metadata_2025 huggingface dataset:
Drawing graphs nicely using simulated annealing
Authors: Davidson Ron , Harel David
Published: July 2002

The paradigm of simulated annealing is applied to the problem of drawing graphs “nicely.” Our algorithm deals with general undirected graphs with straight-line edges, and employs several simple criteria for the aesthetic quality of the result. The algorithm is flexible, in that the relative weights of the criteria can be changed. For graphs of modest size it produces good results, competitive with those produced by other methods, notably, the “spring method” and its variants.
Analysis of benchmark characteristics and benchmark performance prediction
Authors: Saavedra Rafael H. , Smith Alan J.
Published: July 2002

Standard benchmarking provides to run-times for given programs on given machines, but fails to provide insight as to why those results were obtained (either in terms of machine or program characteristics) and fails to provide run-times for that program on some other machine, or some other programs on that machine. We have developed a machine-imdependent model of program execution to characterize both machine performance and program execution. By merging these machine and program characterizations, we can estimate execution time for arbitrary machine/program combinations. Our technique allows us to identify those operations, either on the machine or in the programs, which dominate the benchmark results. This information helps designers in improving the performance of future machines and users in tuning their applications to better utilize the performance of existing machines. Here we apply our methodology to characterize benchmarks and predict their execution times. We present extensive run-time statistics for a large set of benchmarks including the SPEC and Perfect Club suites. We show how these statistics can be used to identify important shortcoming in the programs. In addition, we give execution time estimates for a large sample of programs and machines and compare these against benchmark results. Finally, we develop a metric for program similarity that makes it possible to classify benchmarks with respect to a large set of characteristics.
A graph-constructive approach to solving systems of geometric constraints
Authors: Fudos Ioannis , Hoffmann Christoph M.
Published: July 2002

A graph-constructive approach to solving systems of geometric constraints capable of effeciently handling well-constrained, overconstrained, and underconstrained configurations is presented. The geometric constraint solver works in two phases: in the analysis phase the constraint graph is analyzed and a sequence of elementary construction steps is derived, and then in the construction phase the sequence of construction steps in actually carried out. The analysis phase of the algorithm is described in detail, its correctness is proved, and an efficient algorith to realized it is presented. The scope of the graph analysis is then extended by utilizing semantic information in the form of anlge derivations, and by extending the repertoire of the construction steps. Finally, the construction phase is briefly discussed.
Tolerating latency in multiprocessors through compiler-inserted prefetching
Authors: Mowry Todd C.
Published: July 2002

The large latency of memory accesses in large-scale shared-memory multiprocessors is a key obstacle to achieving high processor utilization.
Software-controlled prefetching
is a technique for tolerating memory latency by explicitly executing instructions to move data close to the processor before the data are actually needed. To minimize the burden on the programmer, compiler support is needed to automatically insert prefetch instructions into the code. A key challenge when inserting prefetches is ensuring that the overheads of prefetching do not outweigh the benefits. While previous studies have demonstrated the effectiveness of hand-inserted prefetching in multiprocessor applications, the benefit of
compiler-inserted
prefetching in practice has remained an open question. This article proposes and evaluates a new compiler algorithm for inserting prefetches into multiprocessor code. The proposed algorithm attempts to minimize overheads by only issuing prefetches for references that are predicted to suffer cache misses. The algorithm can prefetch both dense-matrix and sparse-matrix codes, thus covering a large fraction of scientific applications. We have implemented our algorithm in the SUIF(Stanford University Intermediate Format) optimizing compiler. The results of our detailed architectural simulations demonstrate that compiler-inserted prefetching can improve the speed of some parallel applications by as much as a factor of two.
Informing memory operations
Authors: Horowitz Mark , Martonosi Margaret , Mowry Todd C. , Smith Michael D.
Published: July 2002

Memory latency is an important bottleneck in system performance that cannot be adequately solved by hardware alone. Several promising software techniques have been shown to address this problem successfully in specific situations. However, the generality of these software approaches has been limited because current architecturtes do not provide a fine-grained, low-overhead mechanism for observing and reacting to memory behavior directly. To fill this need, this article proposes a new class of memory operations calledinforming memory operations, which essentially consist of a memory operatin combined (either implicitly or explicitly) with a conditional branch-and-ink operation that is taken only if the reference suffers a cache miss. This article describes two different implementations of informing memory operations. One is based on acache-outcome condition code,and the other is based onlow-overhead traps.We find that modern in-order-issue and out-of-order-issue superscalar processors already contain the bulk of the necessary hardware support. We describe how a number of software-based memory optimizations can exploit informing memory operations to enhance performance, and we look at cache coherence with fine-grained access control as a case study. Our performance results demonstrate that the runtime overhead of invoking the informing mechanism on the Alpha 21164 and MIPS R10000 processors is generally small enough to provide considerable flexibility to hardware and software designers, and that the cache coherence application has improved performance compared to other current solutions. We believe that the inclusion of informing memory operations in future processors may spur even more innovative performance optimizations.
Decay-usage scheduling in multiprocessors
Authors: Epema D. H. J.
Published: July 2002

Decay-usage scheduling is a priority-aging time-sharing scheduling policy capable of dealing with a workload of both interactive and batch jobs by decreasing the priority of a job when it acquires CPU time, and by increasing its priority when it does not use the (a) CPU. In this article we deal with a decay-usage scheduling policy in multiprocessors modeled after widely used systems. The priority of a job consists of a base priority and a time-dependent component based on processor usage. Because t he priorities in our model are time dependent, a queuing-theoretic analysis—for instance, for the mean job response time—seems impossible. Still, it turns out that as a consequence of the scheduling policy, the shares of the available CPU time obtained by jobs converge, and a deterministic analysis for these shares is feasible: We show how for a fixed set of jobs with large processing demands, the steady-state shares can be obtained given the base priorities, and conversely, how to set the base priorities given the required shares. In addition, we analyze the relation between the values of the scheduler parameters and the level of control it can exercise over the steady-state share ratios, and we deal with the rate of convergence. We validate the model by simulations and by measurements of actual systems.
Fundamentals of fault-tolerant distributed computing in asynchronous environments
Authors: Gärtner Felix C.
Published: July 2002

Fault tolerance in distributed computing is a wide area with a significant body of literature that is vastly diverse in methodology and terminology. This paper aims at structuring the area and thus guiding readers into this interesting field. We use a formal approach to define important terms like
fault, fault tolerance
, and
redundancy
. This leads to four distinct forms of fault tolerance and to two main phases in achieving them:
detection
and
correction
. We show that this can help to reveal inherently fundamental structures that contribute to understanding and unifying methods and terminology. By doing this, we survey many existing methodologies and discuss their relations. The underlying system model is the close-to-reality asynchronous message-passing model of distributed computing.
Security of statistical databases
Authors: Schlörer Jan
Published: July 2002

The concept of multidimensional transformation of statistical databases is described. A given set of statistical output may be compatible with more than one statistical database. A transformed database
D
' is a database which (1) differs from the original database
D
in its record content, but (2) produces, within certain limits, the same statistical output as the original database. For a transformable database
D
there are two options: One may physically transform
D
into a suitable database
D
', or one may release only that output which will not permit the users to decide whether it comes from
D
or
D
'. The second way is, of course, the easier one. Basic structural requirements for transformable statistical databases are investigated. The closing section discusses advantages, drawbacks, and open questions.
New file organization based on dynamic hashing
Authors: Scholl Michel
Published: July 2002

New file organizations based on hashing and suitable for data whose volume may vary rapidly recently appeared in the literature. In the three schemes which have been independently proposed, rehashing is avoided, storage space is dynamically adjusted to the number of records actually stored, and there are no overflow records. Two of these techniques employ an index to the data file. Retrieval is fast and storage utilization is low.

In order to increase storage utilization, we introduce two schemes based on a similar idea and analyze the performance of the second scheme. Both techniques use an index of much smaller size. In both schemes, overflow records are accepted. The price which has to be paid for the improvement in storage utilization is a slight access cost degradation.
Interval hierarchies and their application to predicate files
Authors: Wong Kai C. , Edelberg Murray
Published: July 2002

Predicates are used extensively in modern database systems for purposes ranging from user specification of associative accesses to data, to user-invisible system control functions such as concurrency control and data distribution. Collections of predicates, or predicate files, must be maintained and accessed efficiently. This paper describes a dynamic index, called an interval hierarchy, which supports several important retrieval operations on files of simple conjunctive predicates. Search and maintenance algorithms for interval hierarchies are given. For a file of
n
predicates, typical of the kind expected in practice, these algorithms require time equal to
Ο
(log
n
).
Application of Ternary Algebra to the Study of Static Hazards
Authors: Yoeli Michael , Rinon Shlomo
Published: July 2002

This paper is concerned with the study of static hazards in combinational switching circuits by means of a suitable ternary switching algebra. Techniques for hazard detection and elimination are developed which are analogous to the Huffman-McCluskey procedures. However, gate and series-parallel contact networks are treated by algebraic methods exclusively, whereas a topological approach is applied to non-series-parallel contact networks only. Moreover, the paper derives necessary and sufficient conditions for a ternary function to adequately describe the steady-state and static hazard behavior of a combinational network. The sufficiency of these conditions is proved constructively leading to a method for the synthesis of combinational networks containing static hazards as specified. The section on non-series-parallel contact networks also includes a brief discussion of the applicability of lattice matrix theory to hazard detection. Finally, hazard prevention in contact networks by suitable contact sequencing techniques is discussed and a ternary map method for the synthesis of such networks is explained.
Ultimate-Definite and Symmetric-Definite Events and Automata
Authors: Paz A. , Peleg B.
Published: July 2002

New classes of events and finite automata which generalize the noninitial definite class are introduced. These events, called “ultimate definite” (u.d.), “reverse u.d.” and “symmetric definite,” are investigated as to algebraic and closure properties. Effective decision procedures whereby it can be decided whether a given finite automata defines such an event are given and unique canonical representations for these events are derived.
Internal Sorting by Radix Plus Sifting
Authors: MacLaren M. Donald
Published: July 2002

A method is proposed for internal sorting which has the property that the expected time required per record, to sort
n
records with random keys, is a bounded function of
n
. Moreover the storage required in addition to that for the records is only 2
n
address fields. It appears that the method may be a good choice when the number of records to be sorted is of the order of 10,000 or more.

The method consists of partially sorting the records by a radix sort and completing the sort by sifting. In the radix sort, a list type of structure is used to present the distribution of the records.
Roots of Star Events
Authors: Brzozowski J. A.
Published: July 2002

A regular event
W
is a star event if there exists another event
V
such that
W
=
V
*
. In that case,
V
is called a root of
W
. It is shown that every star event has a unique minimum root, which is contained in every other root. An algorithm for finding the minimum root of a regular event is presented, and the root is shown to be regular. The results have applications to languages, codes, canonical forms for regular expressions, simplification of expressions, decomposition of sequential machines, and semigroup theory.
Finding Optimal Demand Paging Algorithms
Authors: Ingargiola Giorgio , Korsh James F.
Published: July 2002

A cost is defined for demand paging algorithms with respect to a formal stochastic model of program behavior. This cost is shown to exist under rather general assumptions, and a computational procedure is given which makes it possible to determine the optimal cost and optimal policy for moderate size programs, when the formal model is known and not time dependent. In this latter case it is shown that these computational procedures may be extended to larger programs to obtain arbitrarily close approximations to their optimal policies. In previous models either unwarranted information is assumed beyond the formal model, or the complete stochastic nature of the model is not taken into account.
Picture Segmentation by a Tree Traversal Algorithm
Authors: Horowitz Steven L. , Pavlidis Theodosios
Published: July 2002

In the past, picture segmentation has been performed by merging small primitive regions or by recursively splitting the whole picture. This paper combines the two approaches with significant increase in processing speed while maintaining small memory requirements. The data structure is described in detail and examples of implementations are given.
An automata-theoretic approach to branching-time model checking
Authors: Kupferman Orna , Vardi Moshe Y. , Wolper Pierre
Published: July 2002

Translating linear temporal logic formulas to automata has proven to be an effective approach for implementing linear-time model-checking, and for obtaining many extensions and improvements to this verification method. On the other hand, for branching temporal logic, automata-theoretic techniques have long been thought to introduce an exponential penalty, making them essentially useless for model-checking. Recently, Bernholtz and Grumberg [1993] have shown that this exponential penalty can be avoided, though they did not match the linear complexity of non-automata-theoretic algorithms. In this paper, we show that
alternating tree automata
are the key to a comprehensive automata-theoretic framework for branching temporal logics. Not only can they be used to obtain optimal decision procedures, as was shown by Muller et al., but, as we show here, they also make it possible to derive optimal model-checking algorithms. Moreover, the simple combinatorial structure that emerges from the automata-theoretic approach opens up new possibilities for the implementation of branching-time model checking and has enabled us to derive improved space complexity bounds for this long-standing problem.
Getting rid of correlations among pseudorandom numbers
Authors: Wegenkittl Stefan , Matsumoto Makoto
Published: July 2002

We consider the impact of discarding and tempering on modern huge period high speed linear generators, and illustrate how a simple strategy yields unexpected — and unwanted — success in a fair coin gambling which is simulated by a recently proposed generator. It becomes clear that discarding is no general rule to get rid of unwanted correlations.
Compiling matrix operations
Authors: Galler Bernard A. , Perlis Alan J.
Published: July 2002

It is unfortunate that almost all of the presently used algebraic languages do not provide the capability of linear algebra. Operations such as the inner product of vectors, the product of two matrices, and the multiplication of a matrix by a scaler must inevitably be written out in detail in terms of the individual components. The reasons usually given for avoiding linear algebra in these languages are (1) the difficulties which would arise in scanning linear algebraic expressions, and (2) the uncertainty involved as to the amount of temporary storage needed during the evaluation of linear algebraic expressions when the program is executed. The purpose of this paper is to show how these two types of difficulties can be overcome. Although suggestions have been made for even further increasing the general capability of ALGOL such as including the ability to form a matrix from a collection of vectors, we shall be content here to consider the ordinary operations of linear algebra. Even if this much becomes available in algebraic languages, considerable progress will have been made. The following remarks constitute a suggestion for the addition to ALGOL of linear algebraic expressions.
An improved index sequential access method using hashed overflow
Authors: Mullin James K.
Published: July 2002

The Index Sequential Access Method (ISAM) is one of the most important file management systems used with moveable head disk devices. This study investigates the use of an unconventional method of treating overflow records. The method is to use hashing techniques to allocate space for such records. If certain conditions are satisfied, this is superior to the conventional ISAM method of chaining the overflow records via linked list techniques. These conditions are: long overflow chains with significant overflow; lack of tight disk space constraints; record keys which are small compared to the total record size; and significant use of the file in the index as opposed to the sequential mode. Using hashed overflow, the time to locate a record is dependent not on the total volume of overflow records as in conventional ISAM, but on the percentage use of space dedicated to overflow records.
An approximate method for generating symmetric random variables
Authors: Ramberg John S. , Schmeiser Bruce W.
Published: July 2002

A method for generating values of continuous symmetric random variables that is relatively fast, requires essentially no computer memory, and is easy to use is developed. The method, which uses a uniform zero-one random number source, is based on the inverse function of the lambda distribution of Tukey. Since it approximates many of the continuous theoretical distributions and empirical distributions frequently used in simulations, the method should be useful to simulation practitioners.
Fen—an axiomatic basis for program semantics
Authors: MacLennan B. J.
Published: July 2002

A formal system is presented which abstracts the notions of data item, function, and relation. It is argued that the system is more suitable than set theory (or its derivatives) for the concise and accurate description of program semantics. It is shown how the system can be used to build composite data types out of simpler ones with the operations of rowing, structuring, and uniting. It is also demonstrated that completely new primitive types can be introduced into languages through the mechanism of singleton data types.

Both deterministic and nondeterministic functions are shown to be definable in the system. It is described how the local environment can be modeled as a data item and how imperative statements can be considered functions on the environment. The nature of recursive functions is briefly discussed, and a technique is presented by which they can be introduced into the system. The technique is contrasted with the use of the paradoxical combinator,
Y
. The questions of local and global environments and of various modes of function calling and parameter passing are touched upon.

The theory is applied to the proof of several elementary theorems concerning the semantics of the assignment, conditional, and iterative statements.

An appendix is included which presents in detail the formal system governing
webs
and
fen
, the abstractions used informally in the body of the paper.
Tree-structured programs
Authors: Wegner Eberhard
Published: July 2002

With this note I hope to bridge the gap between the adherents of structured programming and the devotees of the unrestricted
goto
. I describe a style of programming which combines the advantages of structured programming with nearly all the power of the jump.
An evaluation of statistical software in the social sciences
Authors: Slysz William D.
Published: July 2002

Several hundred college and university computer installations now offer various types of statistical packages for general use. Among those most widely available are OSIRIS, SPSS, BMD, DATA-TEXT, and TSAR. In order to provide users with a basis for selection and use, tests were made for each of these systems, and the results are summarized as to cost and performance.
An overview of the proposed american national standard for local distributed data interfaces
Authors: Burr William E.
Published: July 2002

The Local Distributed Data Interface (LDDI) Project of X3 Technical Committee X3T9 has resulted in three draft proposed American National Standards for a high performance local area network. The proposed standards are organized in accordance with the ISO Reference Model for Open Systems Interconnection and encompass the lowest two protocol layers (data link and physical) of the model, plus a serial broadband coaxial bus interface. The intended application of the LDDI is as a backend network for the interconnection of high performance CPUs and block transfer peripherals such as magnetic disk and tapes. A carrier-sense multiple access with collision prevention (CSMA-CP) distributed bus arbitration protocol is employed. The cable interface supports the attachment of up to 28 ports over a cable distance of 0.5 km (8 ports may be attached to a 1 km cable) at a transfer rate of 50 Mbit/s.
ADA:
Authors: Ichbiah Jean
Published: July 2002

Since the mid-1970s, the U.S. Department of Defense has been laying the groundwork for a major new computer language that may substantially displace FORTRAN and COBOL in the years ahead. With Ada just now starting to be used
, Communications
felt it would be timely to conduct an interview with Jean Ichbiah, the principal designer of this new language. Ichbiah discusses the evolution of Ada, evaluates its success so far, and speculates on its future.
The first course in computer science needs a mathematics corequisite
Authors: Ralston Anthony
Published: July 2002

First-year computer science students need to know and use a considerable amount of mathematics. A corequired course in discrete mathematics is a good solution.
The effect of programming team structures on programming tasks
Authors: Mantei Marilyn
Published: July 2002

The literature recognizes two group structures for managing programming projects: Baker's chief programmer team and Weinberg's egoless team. Although each structure's success in project management can be demonstrated, this success is clearly dependent on the type of programming task undertaken. Here, for the purposes of comparison, a third project organization which lies between the other two in its communication patterns and dissemination of decision-making authority is presented. Recommendations are given for selecting one of the three team organizations depending on the task to be performed.
Computer scientists whose scientific freedom and human rights have been violated
Authors: Minker Jack
Published: July 2002

This report had its genesis before the establishment in February 1980 of the Committee on Scientific Freedom and Human Rights (CSFHR). In 1978 Paul Armer, chairman of the Committee on Computers and Public Policy (CCPP), asked Jack Minker of the University of Maryland to chair a Subcommittee on Human Rights and to prepare a report on the human rights of computer scientists. When CSFHR was formed it was natural to transfer this activity to it since one of the activities of CSFHR, as specified in its charter, is:

Gathering data on systematic violations of scientific freedom and human rights and fully publicizing such data.… Careful attention will be given to assuring the validity of all data.
A critique of the foundations of Hoare style programming logics
Authors: O'Donnell Michael J.
Published: July 2002

Much recent discussion in computing journals has been devoted to arguments about the feasibility and usefulness of formal verification methods. Too little attention has been given to precise criticism of specific proposed systems for reasoning about programs. Whether such systems are to be used for formal verification, by hand or automatically, or as a rigorous foundation for informal reasoning, it is essential that they be logically sound. Several popular rules in the Hoare language are, in fact, not sound. These rules have been accepted because they have not been subjected to sufficiently strong standards of correctness. This paper attempts to clarify the different technical definitions of correctness of a logic, to show that only the strongest of these definitions is acceptable for Hoare logic, and to correct some of the unsound rules that have appeared in the literature. The corrected rules are given merely to show that it is possible to do so. Convenient and elegant rules for reasoning about certain programming constructs will probably require a more flexible notation than Hoare's.
Low contention semaphores and ready lists
Authors: Denning Peter J. , Dennis T. Don , Brumfield Jeffrey A.
Published: July 2002

A method for reducing semaphore and ready-list contention in multiprocessor operating systems is described. Its correctness is established. Its performance is compared with conventional implementations. A ready list implemented as a ring network is proposed and evaluated.
Computational algorithms for product form queueing networks
Authors: Chandy K. Mani , Sauer Charles H.
Published: July 2002

In the last two decades there has been special interest in queueing
networks
with a
product form
solution. These have been widely used as models of computer systems and communication networks. Two new computational algorithms for product form networks are presented. A comprehensive treatment of these algorithms and the two important existing algorithms, convolution and mean value analysis, is given.
Anomalies with variable partition paging algorithms
Authors: Franklin M. A. , Graham G. Scott , Gupta R. K.
Published: July 2002

Five types of anomalous behaviour which may occur in paged virtual memory operating systems are defined. One type of anomaly, for example, concerns the fact that, with certain reference strings and paging algorithms, an increase in mean memory allocation may result in an increase in fault rate. Two paging algorithms, the page fault frequency and working set algorithms, are examined in terms of their anomaly potential, and reference string examples of various anomalies are presented. Two paging algorithm properties, the inclusion property and the generalized inclusion property, are discussed and the anomaly implications of these properties presented.
Optimizing decision trees through heuristically guided search
Authors: Martelli Alberto , Montanari Ugo
Published: July 2002

Optimal decision table conversion has been tackled in the literature using two approaches, dynamic programming and branch-and-bound. The former technique is quite effective, but its time and space requirements are independent of how “easy” the given table is. Furthermore, it cannot be used to produce good, quasioptimal solutions. The branch-and-bound technique uses a good heuristic to direct the search, but is cluttered up by an enormous search space, since the number of solutions increases with the number of test variables according to a double exponential. In this paper we suggest a heuristically guided top-down search algorithm which, like dynamic programming, recognizes identical subproblems but which can be used to find both optimal and quasioptimal solutions. The heuristic search method introduced in this paper combines the positive aspects of the above two techniques. Compressed tables with a large number of variables can be handled without deriving expanded tables first.
The technology of computer center management
Authors: Conte S. D. , Halstead M. H.
Published: July 2002

McFarlan and Nolan have made a strong case for adding a course on information systems administration to the 13 courses proposed by the ACM Curriculum Committee on Computer Education for Management for Graduate Professional Programs in Information Systems. This paper is a report on a course entitled, “The Technology of Computer Center Management,” which has been offered at Purdue for the past four years. The course is suitable either for graduate professional programs in information systems or for graduate professional programs in computer science.
Storage-efficient representation of decimal data
Authors: Chen Tien Chi , Ho Irving T.
Published: July 2002

Usually
n
decimal digits are represented by 4
n
bits in computers. Actually, two BCD digits can be compressed optimally and reversibly into 7 bits, and three digits into 10 bits, by a very simple algorithm based on the fixed-length combination of two variable field-length encodings. In over half of the cases the compressed code results from the conventional BCD code by simple removal of redundant 0 bits. A long decimal message can be subdivided into three-digit blocks, and separately compressed; the result differs from the asymptotic minimum length by only 0.34 percent. The hardware requirement is small, and the mappings can be done manually.
Computer networks in higher education
Authors: Chambers Jack A. , Poore Ray V.
Published: July 2002

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.
A simple linear model of demand paging performance
Authors: Saltzer Jerome H.
Published: July 2002

Predicting the performance of a proposed automatically managed multilevel memory system requires a model of the patterns by which programs refer to the information stored in the memory. Some recent experimental measurements on the Multics virtual memory suggest that, for rough approximations, a remarkably simple program reference model will suffice. The simple model combines the effect of the information reference pattern with the effect of the automatic management algorithm to produce a single, composite statement: the mean number of memory references between paging exceptions increases linearly with the size of the paging memory. The resulting model is easy to manipulate, and is applicable to such diverse problems as choosing an optimum size for a paging memory, arranging for reproducible memory usage charges, and estimating the amount of core memory sharing.
Capability-based addressing
Authors: Fabry R. S.
Published: July 2002

Various addressing schemes making use of segment tables are examined. The inadequacies of these schemes when dealing with shared addresses are explained. These inadequacies are traced to the lack of an efficient absolute address for objects in these systems. The direct use of a capability as an address is shown to overcome these difficulties because it provides the needed absolute address. Implementation of capability-based addressing is discussed. It is predicted that the use of tags to identify capabilities will dominate. A hardware address translation scheme which never requires the modification of the representation of capabilities is suggested. The scheme uses a main memory hash table for obtaining a segment's location in main memory given its unique code. The hash table is avoided for recently accessed segments by means of a set of associative registers. A computer using capability-based addressing may be substantially superior to present systems on the basis of protection, simplicity of programming conventions, and efficient implementation.
Computer science—a vicious circle
Authors: Kandel Abraham
Published: July 2002

In many computer science departments throughout the country, including some interdisciplinary departments, the curriculum has placed increasing emphasis upon applied mathematics and the fundamental nature of computational systems. A set of core courses which usually are fitted into such a program can be found in the report of the ACM curriculum committee on computer science, Curriculum 68 [1]. Some computer science departments have done such a magnificent job of de-emphasizing the importance of the experimental laboratory in their program that their graduates emerge thoroughly unprepared to tackle the intricacies associated with design work in the real-life world—both in software and hardware. This is basically because most computer science departments do not emphasize sufficiently the practical aspects of computational system design and implementation. For example, some students have serious difficulty in designing even a shift register of an 8-4-2-1 counter with ripple carry, not to mention more complicated computer systems. Perhaps even more important, computer science in the academic sense has implemented the “modus ponens” (rule of detachment) from the real-life world and has very little to do with real computers. The relationship between the abstract side of computer science and questions of cost and marketing are hardly ever mentioned in courses.
Numerical mathematics and computer science
Authors: Traub J. F.
Published: July 2002

Numerical mathematics is viewed as the analysis of continuous algorithms. Four of the components of numerical mathematics are discussed. These are: foundations (finite precision number systems, computational compexity), synthesis and analysis of algorithms, analysis of error, programs and program libraries.
Programming systems and languages 1965-1975
Authors: Rosen Saul
Published: July 2002

In spite of impressive gains by PL/I, Fortran and Cobol remain the languages in which most of the world's production programs are written and will remain so into the foreseeable future. There is a great deal of theoretical interest in Algol 68 and in extensible languages, but so far at least they have had little practical impact. Problem-oriented languages may very well become the most important language development area in the next five to ten years. In the operating system area all major computer manufacturers set out to produce very ambitious multiprogramming systems, and they all ran into similar problems. A number of university projects, though not directly comparable to those of the manufacturers, have contributed greatly to a better understanding of operating system principles. Important trends include the increased interest in the development of system measurement and evaluation techniques, and increased use of microprogramming for some programming system functions.
The reallocation of hash-coded tables
Authors: Bays Carter
Published: July 2002

When the space allocation for a hash-coded table is altered, the table entries must be rescattered over the new space. A technique for accomplishing this rescattering is presented. The technique is independent of both the length of the table and the hashing function used, and can be utilized in conjunction with a linear reallocation of the table being rescattered. Moreover, it can be used to eliminate previously flagged deletions from any hash-coded table, or to change from one hashing method to another. The efficiency of the technique is discussed and theoretical statistics are given.
Teaching “about programming”
Authors: Rosin Robert F.
Published: July 2002

This paper presents the goals and organization of a course about programming designed to provide entering students in a graduate program with a cultural enrichment in their professional lives. The students are expected to have taken at least two programming courses prior to this one and, therefore, to be familiar with at least two programming languages, both as students and users.

Teaching someone how to program is similar to teaching him to play a musical instrument: neither skill can be taught—they must be learned. However, the teacher still serves several vital purposes: to present a set of rules for producing well-formed utterances; to offer numerous demonstrations of his own skill; and to function as an involved critic. Finally, the teacher is the source of information about the process in which the student is involved.
Reversible execution
Authors: Zelkowitz M. V.
Published: July 2002

The ability to backtrack, or retrace, the execution of a computer program has gained wider acceptance recently as a desired feature within a programming language. This is particularly useful in two different applications: (1) In debugging systems where the trace output is saved and can be interrogated under programmer control [1, 3]; (2) In artificial intelligence applications where one is trying to prove a certain result. It is frequently necessary to backup the proof and try some alternative path [2].
A language for treating geometric patterns in a two-dimensional space
Authors: Bracchi G. , Ferrari D.
Published: July 2002

In this paper CADEP, a problem-oriented language for positioning geometric patterns in a two-dimensional space, is presented.

Although the language has been specifically designed for the automatic generation of integrated circuit masks, it turns out to be well suited also for such other placement problems as architecture design, urban planning, logical and block diagram representation.

The design criteria, the structure, and the specific features of CADEP are illustrated.
Normalization techniques for handprinted numerals
Authors: Nagy G.
Published: July 2002

A family of pattern standardization techniques based on geometrical projection is applied to a file of digitized handprinted numerals obtained from sales clerks. The principle involves transforming a quadrilateral specified in terms of the convex hull of each pattern into a square. The amount of overlap within each class of characters versus the amount between classes is used to evaluate the degree of normalization achieved with respect to other published methods including size and shear normalization through moments.
Tensor calculations on computer
Authors: Walton John J.
Published: July 2002

In the main text of the paper [
Comm. ACM 9
, 12 (Dec. 1966), 864], a FORMAC program was discussed which is capable of calculating various quantities of interest in tensor calculus. This Appendix is intended as an example of the program output. Christoffel symbols calculated for 12 basic orthogonal coordinate systems are listed.
Computing capabilities at Argentine and Chilean universities
Authors: Finerman Aaron
Published: July 2002

The author reports on a trip to universities in Argentina and Chile during November 1968, describing university conditions and computing activities. As elsewhere, these universities are experiencing student discontent with the status quo and the solutions they are attempting contrast: Argentina is excluding students from participating in university government; Chile is allowing such participation. University computing service and academic activities are limited. The number of computers is small and so is the capacity, none larger than an IBM 360/40; with some exception, computing science academic programs are rare. This situation is by no means attributable to those responsible for computing developments, who strive for excellence; rather the “system” is hard to overcome. Universities, especially those with strong European traditions, adapt slowly to new academic resources and disciplines; superimposed are the severe technological and economic constraints of the developing nation. Consequently, in the absence of conscious government emphasis on strengthening computing capabilities, future progress may be retarded.
Retrieval times for a packed direct access inverted file
Authors: Bayes A. J.
Published: July 2002

This note extends the results obtained by Thomas C. Lowe [1] for the case where the list file is stored in packed form. The notation and terminology used were established by Lowe. In addition, we define
F
(
j
) = ∑

j
-1

i
=1

ƒ(
i
) and write [
x
] for the greatest integer not exceeding
x
.
An interactive graphical display monitor in a batch-processing environment with remote entry
Authors: Bond Alan H. , Rightnour Jerry , Coles L. Steven
Published: July 2002

A graphic monitor program is described. It was developed at Carnegie-Mellon University for the CDC G21 computer, which is a general purpose, batch-processing system with remote entry. The existing G21 system and the graphics hardware are described. The graphic monitor is a resident auxiliary monitor which provides comprehensive managerial capability over the graphical system in response to commands from the human user. It also will respond to commands from a user program through a similar interface, where routine calls take the place of manual actions. Thus the human and program can interact on a symmetrical and equal basis through the medium of the graphic monitor.

The choices made in designing the graphic monitor, given the constraints of the existing hardware and computer system, are discussed.

The structure of the monitor program and the human and program interfaces are described. There is also a transient swapping version with a small resident part, and provision for swapped used submonitors.
Optimal starting values for Newton-Raphson calculation of √x
½
Authors: Moursund David G.
Published: July 2002

The problem of obtaining starting values for the Newton-Raphson calculation of √
x
on a digital computer is considered. It is shown that the conventionally used best uniform approximations to √
x
do not provide optimal starting values. The problem of obtaining optimal starting values is stated, and several basic results are proved. A table of optimal polynomial starting values is given.
Optimization of expressions in Fortran
Authors: Busam Vincent A. , Englund Donald E.
Published: July 2002

A method of optimizing the computation of arithmetic and indexing expressions of a Fortran program is presented. The method is based on a linear analysis of the definition points of the variables and the branching and DO loop structure of the program.

The objectives of the processing are (1) to eliminate redundant calculations when references are made to common sub-expression values, (2) to remove invariant calculations from DO loops, (3) to efficiently compute subscripts containing DO iteration variables, and (4) to provide efficient index register usage.

The method presented requires at least a three-pass compiler, the second of which is scanned backward. It has been used in the development of several FORTRAN compilers that have proved to produce excellent object code without significantly reducing the compilation speed.
Expanding the editing function in language data processing
Authors: Doyle L. B.
Published: July 2002

In automatic abstracting, citation indexing, mechanical translation and other such procedures, editing is required whenever the automatic method leaves something to be desired. This paper discusses the economy of editing as a function of the amount of condensation of text in language processing operations, and then contends that editing can be regarded as an opportunity rather than as an unwelcome necessity.

“Heavy editing,” which goes beyond mere correction and improvement of computer output, is exemplified by the use of a concordance in preparing a survey article or lecture. Other opportunities for heavy editing are described, chief among them being interpretation and expansion of computer output in such processes as factor analysis. Applications are described, such as the quick, unbiased evaluation of a large volume of incoming mail or telegrams, yielding summary reports not possible for either humans or computers to produce alone.
A high-speed sorting procedure
Authors: Frank R. M. , Lazarus R. B.
Published: July 2002

In a recent note
1
, D. L. Shell has described a high-speed sorting procedure for lists contained in internal memory. The method has the great virtues of requiring no additional memory space and being considerably faster than other such methods, which require a time proportional to the square of the list length. The present authors have studied the statistics of Shell's method and have found a minor modification which increases its speed still further.
Interactive execution of distributed algorithms
Authors: Ben-Ari Mordechai
Published: July 2002

DAJ (Distributed Algorithms in Java) is a framework for writing Java programs to implement distributed algorithms. The programs display the data structures at each node and enable the user to interactively construct scenarios. In a learning situation, active interactive execution is preferable to passively watching an animation. Programs have been implemented for commonly taught algorithms, including the Byzantine generals, mutual exclusion, termination, and snapshots. Adding a program for another algorithm requires only general Java programming experience, as the GUI aspects are encapsulated.
Cursor movement during text editing
Authors: Gould John D. , Lewis Clayton , Barnes Vincent
Published: July 2002

Nine participants used a full-screen computer text editor (XEDIT) with an IBM 3277 terminal to edit marked-up documents at each of three cursor speeds (3.3, 4.7, and 11.0 cm/s). These speeds occur when a user continuously holds down an arrow key to move the cursor more than one character position (i.e., in repeat or typamatic mode). Results show that cursor speed did not seem to act as a pacing device for the entire editing task. Since cursor speed is a form of system response, this finding is in contrast with the generally found positive relation between system-response time and user-response time. Participants preferred the Fast cursor speed, however. Overall, more than one-third of all keystrokes were used to move the cursor. We estimate that 9-14 percent of editing time was spent controlling and moving the cursor, regardless of cursor speed.