On multilevel structured program design for process-control systems

Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 165–174, March–April, 1993.     

Picture files for hierarchically structured pictures

For a high-level graphics programming language like PASCAL/Graph[1, 2] which allows a hierarchical structure in the representation of pictures, there must exist an appropriate concept for mapping them on sequential files, and vice versa. This paper describes the internal implementation of pictures in PASCAL/Graph by the picture graph. An important feature is the common subpicture, which means picture information can be reused for several higher level pictures without being duplicated. The representation of such pictures on external files, called picture files, is explained, too. Attention is directed to the correct conversion and reconversion between internal and external representation, so that the status of common subpictures is preserved without any exception. This concept allows many effective operations in constructing pictures as well as storing pictures in a very efficient way, both in main memory and on files. The simple GKS metafile cannot handle these complexly structured pictures; therefore, the more complicated form of picture files (metafiles) is necessary.     

Hector: a hierarchically structured shared-memory multiprocessor

The architecture of the Hector multiprocessor, which exploits current microprocessor technology to produce a machine with a good cost/performance tradeoff, is described. A key design feature of Hector is its interconnection backplane, which can accommodate future technology because it uses simple hardware with short critical paths in logic circuits and short lines in the interconnection network. The system is reliable and flexible and can be realized at a relatively low cost. The hierarchical structure results in a fast backplane and a bandwidth that increases linearly with the number of processors. Hector scales efficiently to larger sizes and faster processors     

Scalable cache consistency for hierarchically structured multiprocessors

This paper presents a new cache consistency scheme for hierarchically structured shared-memory multiprocessors. The scheme is simple, fast and efficient, and it does not require a large amount of state information to be maintained. The scheme exploits the broadcast capability of these systems, but limits the extent of the broadcasts by means of a novel filtering mechanism. As a specific example, it is shown how the proposed cache consistency scheme can be implemented on the Hector multiprocessor architecture. Using trace-driven simulations, we demonstrate that the scheme is scalable and performs well for common applications.     

Relational programs: An architecture for robust real-time safety-critical process-control systems

Software for safety-critical systems, such as avionic, medical, defense, and manufacturing systems, must be highly reliable since failures can have catastrophic consequences. While existing methods, such as formal techniques, testing, and fault-tolerant software, can significantly enhance software reliability, they have some limitations in achieving ultrahigh reliability requirements. Formal methods are not able to cope with specification faults, testing is not able to provide high assurance, and fault-tolerant software based on diverse designs is susceptible to common-mode failures. We present a new approach that starts with a decomposition of the system requirements into a conjunction of subtasks (goals and constraints). The system state space is then projected onto a restricted space that is specialized for a subtask. The control problem corresponding to each subtask is solved and validated in its restricted “view” of the system state space. To allow the programs for the individual subtasks to be easily composed together, the model for each subtask is relational rather than functional, i.e., it represents a set of control trajectories for each input rather than just one trajectory. The overall system is obtained by composing the models for the subtasks using well-defined set intersection and union operations. The relational approach has several significant advantages. With appropriate priority assignments, it provides strong guarantees that the safety-critical components are immune to defects in other components of the system. Also, the system reliability can be rigorously derived from the component reliabilities. This significantly reduces the validation effort since the number of states and transitions in the decomposition is a fraction of those in the overall system. The system can be composed from its components either statically or dynamically; the latter facilitates on-the-fly maintenance as well as incorporation of advanced adaptive and evolving control programs. The paper contains a detailed example to illustrate the relational approach. This revised version was published online in June 2006 with corrections to the Cover Date.     

Comments on the hierarchically structured bin packing problem

We study the hierarchically structured bin packing problem. In this problem, the items to be packed into bins are at the leaves of a tree. The objective of the packing is to minimize the total number of bins into which the descendants of an internal node are packed, summed over all internal nodes. We investigate an existing algorithm and make a correction to the analysis of its approximation ratio. Further results regarding the structure of an optimal solution and a strengthened inapproximability result are given.     

Approximation algorithms for a hierarchically structured bin packing problem

In this paper we study a variant of the bin packing problem in which the items to be packed are structured as the leaves of a tree. The problem is motivated by document organization and retrieval. We show that the problem is NP-hard and we give approximation algorithms for the general case and for the particular case in which all the items have the same size.     

Optimization of structured programs

The class of programs which do not contain goto statements has a structure which lends itself to optimization by an optimizer that is fast, efficient and relatively easy to program. The design of such an optimizer is described, along with some of the results obtained using this optimizer—one such result being that very little code optimization is achieved. The conjecture is made that this is true because gotoless programming languages lend themselves to more compact and concise object code at the source language level.     

Designing structured cobol programs

COBOL is now more than 20 years old and will probably survive to become much older. Since it has some features which are out of date it is desirable to adapt at least the program style to some standards of modern programming languages. The adaption is not only a matter of style but also of costs of program production and program maintenance. This paper presents constructional rules for programming in COBOL which by-pass some of the drawbacks and allow more readable and more maintainable program structures. Finally a postprocessor is presented, that allows verification of the chosen constructional rules and documentation of the resulting programs.     

An empirical approach to evaluating dependency locality in hierarchically structured software systems

In software development, especially component-based software development, dependency locality states that relevant software components should be at shorter distances than irrelevant components. This principle is used together with modularity and hierarchy to guide the design of large-scale complex software systems. In previous work, dependency locality and its correlation with design quality were studied by statically measuring the interactions between software components. This paper presents an empirical approach to evaluating the hierarchical structure of software systems through mining their revision history. Two metrics, spatial distance and temporal distance, are adapted to measure the dependencies between software components. The correlation of spatial distance and temporal distance between software components represents a factor that influences system design quality. More specially, a well designed system hierarchy should have a significant positive correlation while a non-significant positive correlation or a negative correlation would signify design flaws. In an application of this approach, we use Mantel test to study the dependency locality of six software systems from Apache projects.     

An efficient path computation model for hierarchically structured topographical road maps

In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.     

Branch distance optimization of structured programs

One of the functions of code generation (or peephole optimization of generated code) is to find a linear arrangement of code segments such that the sum of branch distances between code segments is minimized. The problem is a generalization of the optimal linear arrangement problem which is known to be NP-hard. However, it has important applications in generating object code for pipeline and cache machines. This paper presents a branch-and-bound method which incorporates a heuristic for deriving a near-optimal initial solution.     

Measuring complexity in structured vs unstructured cobol programs

Measuring programmer productivity and estimating programming time and costs are among the most worrisome and persistent problems facing the programming manager. A key element in both problem areas is program complexity. It has been demonstrated in practice that a measure of program complexity is an indispensable aid in evaluating a programming effort. The purpose of this paper is to present a prototype for a composite measure of program complexity. The paper presents a basis for a technique upon which an objective quantitative evaluation for any program or programming effort could be made.This index of complexity would give the manager a tool for a quantitative assessment of programming efforts so that judgments about the relative merits of programs and programmers can be based on objective data and an objective measure. The measure is applied against a reference group of COBOL programs, several of which were written in a structured programming environment. The index of complexity and the data from which it is derived are used to evaluate the complexity of structured vs unstructured COBOL programming styles.     

Programming errors in traversal programs over structured data

Traversal strategies à la Stratego (also à la Strafunski and ‘Scrap Your Boilerplate’) provide an exceptionally versatile and uniform means of querying and transforming deeply nested and heterogeneously structured data including terms in functional programming and rewriting, objects in OO programming, and XML documents in XML programming.