LIU , Zhen

In this paper, we consider the problem of optimal routing in an interconnection network, called the De Bruijn network, where the sites are linked in the form of a De Bruijn graph. We provide the distance functions for the undirected as well as the directed De Bruijn graphs. The optimal routing problem is then reduced to that of pattern...

It is well-known that most scheduling problems arising from parallel systems are NP-hard, even under very special assumptions. Thus various suboptimal algorithms, in particular heuristics, were proposed in the literature. Worst-case error bounds are established in this note for heuristics of makespan minimization of parallel computations....

Structures of parallel programs are usually modeled by task graphs in the scheduling literature. Such graphs are sometimes obtained while compiling the parallel programs. In many other cases, however, they can be determined only at run time. In this paper, we consider the scheduling of parallel computations whose task graphs are generated at...

Stochastic timed Petri nets are a useful tool in performance analysis of concurrent systems such as parallel computers, communication networks and flexible manufacturing systems. In general, performance measures of stochastic timed Petri nets are difficult to obtain for problems of practical sizes. In this paper, we provide a method to compute...

Disponible dans les fichiers attachés à ce document

Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be represented by a task graph, where vertices represent tasks and arcs represent the communications between the tasks. An interprocessor communication time incurs when two tasks assigned to two different processors have to communicate. Such...

Disponible dans les fichiers attachés à ce document

In this paper we address the problem of optimal scheduling in a multi-queue single-server (MQSS) model. The server visits N queues in an arbitrary manner. Each queue is visited for a random period of time whose duration is sampled in advance. At the end of a visit period, either all customers of the attended queue leave the system (variant I),...

General formulas are proposed to quantify the effects of changing the arrival and service rates in the so-called BCMP network. These formulas relate the derivative of the expectation of any function F of the state of the network with respect to any arrival/service rate in the network, to known functions of the state of the network. As an...

Disponible dans les fichiers attachés à ce document

Disponible dans les fichiers attachés à ce document

We consider optimal load balancing in a distributed computing environment with several homogeneous unreliable processors that have limited state information. Each processor receives its own arrival process of tasks from outside users, some of which can be redirected to the other processors. Processing times are {\em iid} and arbitrarily...