In systems where job service demands are only known probabilistically, there is very little to distinguish between jobs. Therefore, no universal optimum scheduling strategy or algorithm exists. If the distribution of job times is known, then the residual time (expected time remaining for a job), based on the service it has already received, can be calculated. In a detailed discrete event simulation, we have explored the use of this function for increasing the probability that a job will meet its deadline. We have tested many different distributions with a wide range of sigma2and shape, four of which are reported here. We compare with RR and FCFS, and find that in all distributions studied our algorithm performs best. We also studied the use of two slow servers versus one fast server, and have found that they provide comparable performance, and in a few cases the double server system does better

Scheduling can require analyzing not only the total computation time of a task, but also the remaining execution time, R(t)/sub /spl Delta/t/, after accumulated time /spl Delta/t. Often a software program's execution time is characterized by a single value (mean). When scheduling is based on partial execution (a common scenario in multimedia systems) a more accurate estimation of remaining time (R(t)/sub /spl Delta/t/) is desired than can be obtained from just the initial mean value, in order to have effective scheduling decisions. The remaining time approach can provide more accurate estimation, and therefore more effective scheduling, in time-sensitive situations. We developed an analytical model for computing expected remaining execution time, (R(t)/sub /spl Delta/t/)~ , of software programs from their execution time and probability distributions. To implement the equations, we further designed an algorithm that computes (R(t)/sub /spl Delta/t/)~ for operating system scheduling applications. We proved that the real time execution complexity of the algorithm is O(1) and is, therefore, independent of the size of the distribution. Our method of more accurate estimate of (R(t)/sub /spl Delta/t/)~ implies expect better scheduling performance in applications where remaining execution time is used, especially in CPU scheduling.

A methodology and related software design environment for the development of performance-engineered object-oriented distributed systems is essential. In this research, a performance-engineered design framework that utilizes the system architecture and object-oriented software design techniques of the Unified Modeling Language (UML) and the architecture of the Hierarchical Performance Model (HPM) is developed to assist designers in evaluating alternatives for performance enhancement. The developed framework integrates the architectural, structural and behavioral components of an application with the performance parameters required for performance model generation and evaluation during the software design process. Performance views for the presentation of performance information and selection of critical path scenarios along with an example are briefly described.

Performance modeling and evaluation techniques are essential when designing and implementing distributed software systems. Constructing performance models for such systems can require significant effort. This paper presents Hierarchical Performance Modeling as a technique to model performance for different layers of abstraction. Once the system architecture and software functionality have been specified, this model supports performance model generation for the evaluation and analysis of computation delays of software processes, communication delays of distributed software architectures, and hardware platform alternatives. A simplified example is presented to illustrate the concepts of the Hierarchical Performance Model.

The problem of obtaining approximate formulas for mean resequencing waiting times of M/GI/c queueing systems is considered. Two assumptions, commonly used in the study of M/GI/c systems, to derive the formulas are adopted. The formulas are quite accurate and the accuracy increases as c becomes larger. The relative differences between simulation results and the ones calculated by the formulas are below 4%, even for larger server utilization ( rho ). For small rho , the differences are below 1%. Both small rho , the differences are below 1%. Both numerical and simulation results indicate that when the squared coefficient of variation of service time distribution is greater than 1, the mean resequencing waiting time is likely to be very large.>

The authors investigate the modeling and analysis of time cost behavior of parallel computations. It is assumed parallel computations reside in a computer system in which there is a limited number of processors, all the processors have the same speed, and they communicate with each other through a shared memory. It has been found that the time costs of parallel computations depend on the input, the algorithm, the data structure, the processor speed, the number of processors, the processing power allocation, the communication, the execution overhead, and the execution environment. The authors define time costs of parallel computations as a function of the first seven factors as listed. The computation structure model is modified to describe the impact of these seven factors on time cost. Techniques based on the modified computation structure model are developed to analyze time cost. A software tool, TCAS (time cost analysis system), that uses both the analytic and the simulation approaches is designed and implemented to aid users in determining the time cost behavior of their parallel computations.>

Abstract In this paper, we present a software system, OPAS (Optimal Allocation System), that incorporates the optimal allocation policy in the analysis of the time‐cost behaviour of parallel computations. OPAS assumes that the underlying system which supports the executions of parallel computations has a finite number of processors, that all the processors have the same speed and that the communication is achieved through a shared memory. OPAS defines the time cost as a function of the input, the algorithm, the data structure, the processor speed, the number of processors and the processing power allocation. In analysing the time cost of a computation, OPAS first uses the optimal allocation policy that we developed previously to determine the amount of processing power each node receives and then derives the computation's time cost. OPAS can evaluate different time‐cost behaviours, such as the minimum time cost, the maximum time cost, the average time cost and the time‐cost variance. It can also determine the speed‐up and efficiency, and plot the time‐cost curve and time‐cost distribution.

A software experimental analysis approach that unifies static and dynamic techniques is presented. The goal was to develop practical means to obtain precise, in-depth, and relevant performance information, especially execution time, for guiding design decisions. First, computation cost functions of a program are derived. This is done by modeling the program using the computation structure model and then applying a flow analysis technique to derive the program's cost function. In addition, program instrumentation techniques are employed to measure control flows and to trace program variables. Finally, precise execution-time information is computed by evaluating the cost function against the measured control flows. The three classes of parameters (execution time, control flow and program variables) can be analyzed selectively and interactively; this gives much insight about an individual design alternative's actual behavior. To cope with tedious and frequent analyses of large and complex software, a tool COPES, was built that automates the static and dynamic techniques required. The implementation and usage of this tool are illustrated.>

An architecture assessment environment is proposed for the design and performance evaluation of massively parallel real-time systems. Included are the major inherent phases of design activity and performance analysis that are implicit in the real-time design process. The major contribution is the definition of a comprehensive methodology and corresponding software support tools to allow and assist a designer in his/her development and assessment of parallel real-time systems. Included in the formulation is the ability to specify either homogeneous or heterogeneous hardware architectures, and to provide a basis for determining performance estimates early in the design process which could allow and direct intelligent design decisions. In addition, the methodology presented can be used to support the entire system life-cycle.>

The process connectivity constraints and the resulting impact on the computation structure are considered. Within these constraints, an approach is presented for restructuring a set of subtasks with precedence constraints and stochastic properties into alternative parallel structures that can be scheduled in parallel distributed systems. A queuing model is used to evaluate the module response time and its resource cost. This model takes into consideration both the communication and the synchronization delays. Finally, an algorithm for determining feasible schedules (that meet designer performance constraints) in order of minimum resource cost is developed.>

HyperCard is an object-oriented, graphic programming language developed by Apple Computer Inc. for its Macintosh computers. A description is given of the use of HyperCard in the development of prototype human-computer interfaces for CASE systems. Direct manipulation creating static graphic components and artificial delays, are discussed.>

Investigation into real-time performance analysis and allocation of system resources to meet throughout and response time requirements has resulted in a proposed methodology for structuring software for real-time distributed systems. A queueing network model is used to estimate real-time performance for alternative software partitions, and those partitions which can satisfy user performance requirements while requiring minimal resources are determined. The current work is limited to feed-forward, pipelined structures. Partition blocks are formed by merging user-specified modules, and the required processing power to meet user requirements is then determined. A two queue model, representing module service and communications, is analyzed using queueing network approximation. The results show that the optimal solution set can be determined using a branch and bound approach. An example of the application of the results to a real system is provided. The results have been implemented as a user-interactive software structuring tool.

Abstract In this paper, we present a software tool, RTS (real time simulator), that analyses the time cost behaviour of parallel computations through simulation. It is assumed in RTS that the computer system which supports the executions of parallel computations has a limited number of processors all processors have the same speed and they communicate with each other through a shared memory. In RTS, the time cost of a parallel computation is defined as a function of the input, the algorithm, the data structure, the processor speed, the number of processors, the processor power allocation, the communication and the execution environment. How RTS models the time cost is first discussed in the paper. In the model, a locking technique is used to manipulate the access to the shared memory, processing power is equally allocated among all the operations that are currently being performed in parallel in the computer system, and the number of operations in the execution environment of a parallel computation changes from time to time. How RTS works and how the simulation is used to do time cost analysis are also discussed.

A multiple microprocessor system is described which was developed for real-time detection and classification of railroad track flaws. Multiple processors were necessary to achieve the desired test vehicle velocity while maintaining the desired density (rate) of testing. The system is organized logically as a tree-structured pipeline of processing stages where the effective data rate from data input toward classification decision output is successively reduced as processing function potential is increased. A corresponding partitioning of the pattern recognition process was organized as a set of hierarchies, where successive patterns are modeled as regular probabilistic grammars and their recognizers implemented as finite state procedures. Interprocessor communications was achieved using shared (2-port) memories. A system prototype was designed and implemented, using real-time data from earlier work to ensure a performance level equivalent to a vehicle velocity of 40 km/h. The resulting system, while applied to a railroad track problem, is applicable to other real-time environments, with suitable parameterization.

In the last few years advancements in VLSI technology have brought about practical research consideration of distributed computer system applications. A significant question is, "What potential improvements may be expected in an algorithm when its control structure is altered to maximize its internal parallelism?" This paper develops a general model for this area based on computation structures, defines algorithms to extract parallelism, and examines an experimental test set of programs in PL/1 to assess their potential performance improvement in expected execution time.

A mixed mode sequential machine (MSM) is defined as a representation in which both synchronous (clocked) and asynchronous (unclocked) state transitions are allowed. The intent of the representation is to allow designers to consider both types of transitions in a single structure, thereby promoting the use of LSI devices such as ROM's or PLA's to resolve the realization question. The approach is thus different from conventional design methods, in which asynchronous problems are treated separately with separate devices. The problems of state reduction, state assignment, and realization are covered. Of particular note is the development of a ROM implementation, which allows both clocked and unclocked transitions to occur.

The application of microprogrammed READ-ONLY memories in the design of asynchronous sequential networks is investigated. Variations of single-transition time (STT) state assignments are shown to be applicable to the problem of assigning memory addresses to a memory representation of an asynchronous network. Design algorithms are developed which allow the implementation of an asynchronous sequential network as a READ-ONLY memory. Two operating modes are considered: normal asynchronous operation and a self-clocked mode in which sequential outputs are allowed on a single-input change, thus providing a means of implementing functions normally achieved with synchronous (clocked) networks. In addition the practical timing constraints of the proposed methods are considered.

An engineering-oriented performance model of a computation is developed by extending the concept of a computation structure to cover the performance costs appropriate to software modelling. The model allows both serial and parallel (multiprocessor) configurations,and the evaluation of both time space parameters for alternate realizations. A brief discussion on the use of the model as a mechanism to guide the performance optimisation of programs is included.

This paper investigates a potential application of microprogrammable memories to the problem of sequential network synthesis and computer design. It is shown that by allowing a controllable amount of memory redundance, a microprogrammed emulation of a state table can be organized such that decision branches in the microprogram are achieved in an immediate multiport manner, without the need of additional branch steps in the microprogram, thus increasing operational speed. A design technique is developed which, for a given state table, allows a minimum number of memory address variables to be used while minimizing the dependence of the variables on both the input and current state information. This technique has immediate practical application in the design of sequential networks, and is shown to be feasible in the controller design of a general purpost computer.

A predictive model is presented that represents the human as an information processor by mathematically simulating the results of past psychological research in choice reaction time, memory storage/ retrieval, and perceptual information processing. Both discrimination and identification tasks are characterized by ideal decisions with additive Gaussian noise. In an information processing task both presented and stored information are processed using a sequential dimensional procedure to identify a presented stimulus. This technique is shown to produce a logarithmic variation in response time as a function of the number of stimuli being presented. The model's simulation of a three-dimensional visual identification task was compared with the experimental results of three subjects. The equipment used consisted of a computer-controlled discrete dot display; the dimensions used were horizontal and vertical extent and the percentage of dots present in a given area. It was found that the simulation reflected the subjects' behavior in both decision accuracy and response time for different sets of a priori probabilities.