Informatica

This paper deals with load balancing of parallel algorithms for distributed-memory computers. The parallel versions of BLAS subroutines for matrix-vector product and LU factorization are considered. Two task partitioning algorithms are investigated and speed-ups are calculated. The cases of homogeneous and heterogeneous collections of computers/processors are studied, and special partitioning algorithms for heterogeneous workstation clusters are presented.

In this paper we consider the problem of solving 3D diffusion problems on distributed memory computers. We present a parallel algorithm that is suitable for the number of processors less or equal 8. The pipelining method is used to enlarge the number of processors till 64. The computational grid decomposition method is proposed for heterogenous clusters of workstations which preserves the load balancing of computers. The numerical results for two clusters of workstations are given.

We consider a possibility of automating the analysis of a computer program realizing the objective function of an extremal problem, and of distributing the calculation of the function value into parallel processes on the basis of results of the analysis. The first problem is to recognize the constituent parts of the function. The next one is to determine their computing times. The third problem is to distribute the calculation of these parts among independent processes. A special language similar to PASCAL has been used to describe the objective function. A new scheduling algorithm, seeking to minimize the maximal finishing time of processing units, was proposed and investigated. Experiments are performed using a computer network.

In the application of Dantzig–Wolfe decomposition to block-angular linear programming problems with R natural blocks. it is possible to have from 1 to R subproblems structurally while solving all R independent subproblems computationally. Early literature on the topic was inconclusive regarding the relative merits of such formulations. This paper attempts clarification by characterizing the significance of the degree of decomposition as well as presenting extensive empirical results.

In this paper, we present an effective performance driven placement with global routing algorithm for macro cells. Our algorithm uses a hierarchical, divide and conquer, quad-partitioning approach. The quad-partitioning routine uses the Tabu Search technique. Our algorithm uses the concept of proximity of regions to approximate the interconnection delays during the placement process. In addition, our algorithm can handle modules whose positions are fixed or are restricted to a particular subregion on the layout frame. Our experimental results indicate the superiority of our placement method in terms of quality of solution and run time when compared to Lin and Du (1990).

The queueing system theory is well developed. Such an important problem as the efficient of customer service in efficiency a multichannel queueing system with different productivity of service channels is well developed, too. Exact formulas are obtained from which the loss probability can be computed (if the input stream of customers distributed as Poisson and service time of the customer is the exponential service time). However, these formulas are very complex. So, in this paper, two theorems are proved, in which upper and lower estimates of the loss probability are presented. These estimates are simple formulas that don't become more complex with the growing number of service channels in the queueing system.

It is desirable in many applications, that a set of cooperating processes do not loose their coordination due to failures. This paper presents a fault-tolerant protocol for a network of processors, which form a logical ring on a physical broadcast medium. The presented protocol makes possible for a set of processes to reestablish their normal operation after transient or permanent process failure or transient communication failures. The protocol is described, model for the system is developed, and in the framework of this model it is proved, that the system reaches a stable and correct configuration in finitely many steps after failure.

This paper presents the framework for well-understood domain analysis as a decisive stage for the successive process of domain-specific software tools building. Specific features of the well-understood domain analysis are formulated. Initial model of the tools to be built and the analysis process are described. Analysis is performed with the reusability concept in mind and as a result essential domain knowledge is extracted. The latter is defined by a term “domain knowledge template”.