Technical Reports

The ICICS/CS Reading Room

1981 UBC CS Technical Report Abstracts

TR-81-01 Distributed I/O Using an Object-Based Protocol, January 1981 David R. Cheriton

The design of a distributed I/O system is described. The system is distributed in being implemented by server processes, client processes and a message communication mechanism between them. Data transfer between processes is achieved using a ``connectionless'' object-based protocol. The concept of \underline{file} is generalized to that of a \underline{view} of an object or activity managed by a server. This allows many objects, including application-defined objects, to be viewed or accessed within the program I/O paradigm. Files are instantiated as \underline{file instance} objects to allow access to the associated data. Conventional byte-stream program input/output facilities are supported by a subroutine library which makes the message-based implementation transparent to applications.

TR-81-02 Collocation for Singular Perturbation Problems I: First Order Systems with Constant Coefficients, February 1981 Uri Ascher and R. Weiss

The application of collocation methods for the numerical solution of singularly perturbed ordinary differential equations is investigated. Collocation at Gauss, Radau and Lobatto points is considered, for both initial and boundary value problems for first order systems with constant coefficients. Particular attention is paid to symmetric schemes for boundary value problems; these problems may have boundary layers at both interval ends. .br Our analysis shows that certain collocation schemes, in particular those based on Gauss or Lobatto points, do perform very well on such problems, provided that a fine mesh with steps proportional to the layers' width is used in the layers only, and a coarse mesh, just fine enough to resolve the solution of the reduced problem, is used in between. Ways to construct appropriate layer meshes are proposed. Of all methods considered, the Lobatto schemes appear to be the most promising class of methods, as they essentially retain their usual superconvergence power for the smooth, reduced solution, whereas Gauss-Legendre schemes do not. .br We also investigate the conditioning of the linear systems of equations arizing in the discretization of the boundary value problem. For a row equilibrated version of the discretized system we obtain a pleasantly small bound on the maximum norm condition number, which indicates that these systems can be solved safely by Gaussian elimination with scaled partial pivoting.

TR-81-03 On Pseudo-Similar Vertices in Trees, April 1981 David G. Kirkpatrick, Maria M. Klawe and D. G. Corneil

Two dissimilar vertices $u$ and $v$ in a graph $G$ are said to be pseudo-similar if $G \backslash u \cong G \backslash v$. A characterization theorem is presented for trees (later extended to forests and block-graphs) with strictly pseudo-similar (i.e. pseudo-similar but dissimilar) vertices. It follows from this characterization that it is not possible to have three or more mutually strictly pseudo-similar vertices in trees. Furthermcre, pseudo-similarity combined with an extension of pseudo-similarity to include the removal of first neighbourhoods of vertices is sufficient to imply similarity in trees. Neither of these results holds if we replace trees by arbitrary graphs.

TR-81-04 On Spline Basis Selection for Solving Differential Equations, April 1981 Uri Ascher, S. Pruess and Robert D. Russell

The suitability of B-splines as a basis for piecewise polynomial solution representation for solving differential equations is challenged. Two alternative local solution representations are considered in the context of collocating ordinary differential equations: ``Hermite-type'' and ``monomial''. Both are much easier and shorter to implement and somewhat more efficient than B-splines. .br A new condition number estimate for the B-splines and Hermite-type representations is presented. One choice of the Hermite-type representation is experimentally determined to produce roundoff errors at most as large as those for B-splines. The monomial representation is shown to have a much smaller condition number than the other ones, and correspondingly produces smaller roundoff errors, especially for extremely nonuniform meshes. The operation counts for the two local representations considered are about the same, the Hermite-type representation being slightly cheaper. It is concluded that both representations are preferable, and the monomial representation is particularly recommended.

TR-81-05 The Application of Optimal Stochastic Control Theory in Computer System Load Regulation, June 1981 Samuel T. Chanson and Raymond Lo

A method using some results and techniques of Optimal Stochastic Control Theory is introduced to compute the optimal admission policy for paged batch-interactive computer systems. The admission policy determines the optimal number of batch and terminal jobs that should be activated at each system state to maximize throughput. The system state is defined as the vector (N1,N2) where N1 and N2 are respectively the total number of terminal and batch jobs in the system. Thus the policy is adaptive to workload variation. As well, the quality of service given to each class of jobs (specifically their mean response times) can be adjusted by choosing a suitable weight for the terminal jobs. A large weight reduces the mean response time of the terminal jobs at the expense of the mean batch response time while maintaining the total system throughput at its maximum level. .br Unlike most existing adaptive control algorithms, the approach is based on mathematical modelling and its extension to cover the case of more than two classes of jobs is straightforward.

TR-81-06 The Computer and the State, July 1981 Richard S. Rosenberg

It is obviously difficult (if not impossible) to predict the impact on society of technological innovation. However, it is clear that such major events as the industrial revolution recreate society in a profound and enduring manner. In our own time, the development of the computer promises to transform dramatically the major industrial countries of the world. The resulting effects on the so-called Third World countries will hardly be less significant. .br The purpose of this paper is twofold. First, we wish to catalogue many of the ways computers have affected and are likely to affect our daily lives. A second purpose is to employ this analysis to explore the effect of the massive ``computerization'' of society on a number of its institutions. It is hoped that the material provided will be useful to those whose major concern is the evolution of the modern state in response to technological innovation.

TR-81-07 On the Complexity of General Graph Factor Problems, August 1981 David G. Kirkpatrick and P. Hell

For arbitrary graphs G and H, a G-factor of H is a spanning subgraph of H composed of disjoint copies of G. G-factors are natural generalizations of l-factors (or perfect matchings), in which G replaces the complete graph on two vertices. Our results show that the perfect matching problem is essentially the only instance of the G-factor problem that is likely to admit a polynomial time bounded solution. Specifically, if G has any component with three or more vertices then the existence question for G-factors is NP-complete. (In all other cases the question can be resolved in polynomial time.) .br The notion of a G-factor is further generalized by replacing G by an arbitrary family of graphs. This generalization forms the foundation for an extension of the traditional theory of matching. This theory, whose details will be developed elsewhere, includes, in addition to further NP-completeness results, new polynomial algorithms and simple duality results. Some indication of the nature and scope of this theory are presented here.

TR-81-08 Solvable Cases of the Travelling Salesman Problem, September 1981 Paul C. Gilmore

This paper is a chapter in a book on the travelling salesman problem edited by Eugene L. Lawler, Jan Karel Lenstra and Alexander H.G. Rinooy Kan. By a solvable case of the travelling salesman problem is meant a case of the distance matrix for which a polynomial algorithm exists. In this paper several previously known special cases are related and extended. Further, an upper bound is obtained on the cost of an optimal tour for a broad class of matrices.

TR-81-09 Strategy-Independent Program Restructuring Based on Bounded Locality Intervals, August 1981 Samuel T. Chanson and Bernard Law

A new program restructuring algorithm based on the phase/transition model of program behaviour is presented. The scheme places much more emphasis on those blocks in the transition phases in the construction of the connectivity matrix than the existing algorithms. This arises from the observation that the page fault rate during the transition phases is several orders of magnitude higher than that during the major phases. The strategy is found, for our reference strings, to outperform the critical working set strategy (considered to be the current best), by non-negligible amounts. Furthermore, the overhead involved is lower than that of CWS and not much higher than that of the Nearness method which is the simplest scheme known. Being strategy-independent, it also seems to respond better than CWS when the memory management strategy used is not the working set policy.

TR-81-10 Pitfalls in the Numerical Solution of Linear Ill-Posed Problems, January 1981 James M. Varah

Very special computational difficulties arise when attempting to solve linear systems arising from integral equations of the first kind. We examine here existence and uniqueness questions associated with so-called \underline{reasonable} solutions for such problems, and present results using the best- known methods on inverse Laplace transform problems. We also discuss the choice of free parameters occurring in these methods, from the same point of view.

TR-81-11 Optimal Macro-Scheduling, August 1981 Samuel T. Chanson and Prem Swarup Sinha

A multi-class macro-scheduler is described in this paper. The scheduler periodically determines the number of jobs from each class that should be activated to minimize a weighted sum of the mean system residence time without saturating the system. The computation is based on the estimated system workload in the next interval. Thus it is adaptive to workload variation. The service provided to each class (specifically, the mean response time) may be adjusted by changing the weight associated with the job class. .br The scheme is based on mathematical modelling. The solution is obtained through the use of operational analysis method and optimization theory. Exponential smoothing technique is employed to reduce the error of estimating the value of the model parameters. From our simulation results, the scheme appears to be both stable and robust. Performance improvement over some of the $S and the Knee criteria) is significant under some workloads. The overhead involved in its implementation is acceptable and the error due to some of the assumptions used in the formulation and solution of the model are discussed.

TR-81-12 Upper Bounds for Sorting Integers on Random Access Machines, September 1981 David G. Kirkpatrick and Stefan Reisch

Two models of Random Access Machines suitable for sorting integers are presented. Our main results show that i) a RAM with addition, subtraction, multiplication, and integer division can sort $n$ integers in the range $[0,2^{cn}]$ in $O(n \log c + n)$ steps; ii) a RAM with addition, subtraction, and left and right shifts can sort any $n$ integers in linear time; iii) a RAM with addition, subtraction, and left and right shifts can sort $n$ integers in the range $[0,n^{C}]$ in $O(n \log c + n)$ steps, where all intermediate results are bounded in value by the largest input.

TR-81-13 Optimal Search in Planar Subdivisions, January 1981 David G. Kirkpatrick

A planar subdivision is any partition of the plane into (possibly unbounded) polygonal regions. The subdivision search problem is the following: given a subdivision $S$ with $n$ line segments and a query point $p$, determine which region of $S$ contains $p$. We present a practical algorithm for subdivision search that achieves the same (optimal) worst case complexity bounds as the significantly more complex algorithm of Lipton and Tarjan, namely $O(\log n)$ search time with $O(n)$ storage. Our subdivision search structure can be constructed in linear time from the subdivision representation used in many applications.

TR-81-14 A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, September 1981 Raimund Seidel

Finding the convex hull of a finite set of points is important not only for practical applications but also for theoretical reasons: a number of geometrical problems, such as constructing Voronoi diagrams or intersecting hyperspheres, can be reduced to the convex hull problem, and a fast convex hull algorithm yields fast algorithms for these other problems. .br This thesis deals with the problem of constructing the convex hull of a finite point set in $R^{d}$. Mathematical properties of convex hulls are developed, in particular, their facial structure, their representation, bounds on the number of faces, and the concept of duality. The main result of this thesis is an $O(n \log n + n^{\lfloor(d+1)/2\rfloor})$ algorithm for the construction of the convex hull of $n$ points in $R^{d}$. It is shown that this algorithm is worst case optimal for even $d \geq 2$.

TR-81-15 On the Shape of a Set of Points in the Plane, September 1981 H. Edelsbrunner, David G. Kirkpatrick and Raimund Seidel

A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, called ``shapes'', which seem to capture the intuitive notion of ``fine shape'' and ``crude shape'' of point sets. .br Additionally, close relationships with Delaunay triangulations are revealed and, relying on these results, an optimal algorithm that constructs ``shapes'' is developed.

TR-81-16 Optimization Techniques in Computer System Design \& Load Control, September 1981 Prem Swarup Sinha

Analytic modelling has proven to be cost-effective in the performance evaluation of computer systems. So far, queueing theory has been employed as the main tool. This thesis extends the scope of analytic modelling by using optimization techniques along with queuing theory in solving the decision-making problems of performance evaluation. Two different problems have been attempted in this thesis. .br First, a queueing network model is developed to find the optimal capacities and speeds of the memory levels in a memory hierarchy system operating in a multiprogrammed environment. Optimality is defined with respect to mean system response time under a fixed cost constraint. It is assumed that the number of levels in the hierarchy as well as the capacity of the lowest level are known. The effect of storage management strategy and program behaviour are characterised by the miss ratio function which, together with the device technology cost function, is assumed to be represented by power functions. It is shown that the solution obtained is globally optimal. .br Next, two adaptive schemes, SELF and MULTI-SELF, are developed to control the flow of jobs in a multiprogrammed computer system. They periodically determine the number of jobs from each class that should be activated to minimize the mean system residence time without saturating the system. The computation is based on the estimated system workload in the next interval. An exponential smoothing technique is used to reduce the error in estimating the values of the model parameters. The service provided to each class (specifically, the mean response time) may be adjusted by changing the weight associated with the job class. From our simulation results, the schemes appear to be both stable and robust. Performance improvement over $S and the Knee criteria) is significant under some workloads. The overhead involved in its implementation is acceptable and the error due to some of the assumptions in the formulation and solution of the model are discussed.

If you have any questions or comments regarding this page please send mail to