14587701
Routing and Transmitting Problems in de Bruijn Networks
De Bruijn graphs, both directed and undirected, have received considerable attention as architecture for interconnection networks. In this paper, we focus on undirected de Bruijn networks of radix d and dimension 0, denoted by UB(d, 0). We first discuss the shortest-path routing problem. We present properties of the shortest paths between any two vertices of UB(d, 0) and propose two shortest-path routing algorithms, one of which has linear time complexity. Secondly, we study the transmitting problem. We establish a lower bound for the optimal transmitting time which implies in particular that the optimal transmitting problem is trivial for UB(d, 0) when d/spl ges/5. We present a transmitting scheme on undirected binary de Bruijn networks UB(2, n) with transmitting time n-1 for n/spl ges/5, and conjecture that the optimal transmitting time is n-1 for UB(2, n), and n for U8(3, n) and UB(4, n).
17293889
Complexity of Task Graph Scheduling with Fixed Communication Capacity
Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be modeled by a task graph, where vertices represent tasks and arcs the communications between tasks. An interprocessor communication time incurs when two tasks assigned to two different processors have to communicate. Such a scheduling problem has recently been studied in the literature, mostly for the case where interprocessor communication times are fully determined. In this paper, we consider the scheduling problem with communication resource constraints. More specifically, we consider the case where all interprocessor communications take place on a network of bounded capacity. We consider two variants of the problem: communications with independent-data semantics and common-data semantics. We show that even for very specific subproblems, viz. scheduling of general graphs on two processors and scheduling of binary trees on an infinite number of processors, the minimization of the makespan of parallel programs in such a multiprocessor system is strongly -hard. We first establish the results for the case of capacity 1, referred to as the single-bus system. We then extend the results to the more general case of fixed communication capacities. As a consequence, the general scheduling problem of parallel programs with communication resource constraints is strongly -hard. These results are to be contrasted with the corresponding scheduling problems without contraint on the communication capacity, where the two-processor case has unknown time complexity and the infinite-processor case is polynomial. Our results are also extended to the case of broadcasting communications, and can be applied to multiprocessor systems with shared memory.
7929531
Closed-Form Deterministic End-to-End Performance Bounds for the Generalized Processor Sharing Scheduling Discipline
The Generalized Processor Sharing (GPS) schedulingdiscipline is an important scheduling mechanism that can support both class isolation and bandwidth sharing among different service classes, thus making itan appealing choice for networks providing multiple services with Quality-of-Service guarantees. In this paper, we study a broad classof GPS networks known as Consistent Relative Session Treatment}(CRST) GPS networks and establish closed-form end-to-end performance boundsfor CRST GPS networks. This result generalizes the results of Parekhand Gallager (1994) where simple, closed-form end-to-end performancebounds are derived for a special sub-class of CRST GPS networks, theso-called Rate Proportional Processor Sharing (RPPS) GPS networks, but performance bounds for the general CRST GPS networks do not haveclosed-form. Our result is obtained through the notion of CRSTpartition, which in fact yields a broader class of CRST GPS networksthan the one originally defined in (Parekh and Gallager, 1993). Moreover,our approach is quite general. It not only applies to the deterministicanalysis of GPS networks, but can also be employed in the study of GPSnetworks in a stochastic setting.
12816052
Worst-Case Analysis of Scheduling Heuristics of Parallel Systems
Abstract 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 paper for heuristics of makespan minimization of parallel computations. Different parallel computation models are investigated, including interprocessor communication, task duplication, multiprocessor tasks and parallel tasks. Due to the heterogeneity of these systems, scheduling heuristics can be far away from the optimal solutions. These bounds provide insights to the design of scheduling heuristics in order to obtain good performance guarantee than arbitrary heuristics. Moreover, the performance guarantee of these special heuristics is independent of model parameters such as the maximal duplication degree, processor requirement and parallelization degree.
17231470
Dynamic scheduling of parallel computations
Structures of parallel programs are usually represented by task graphs in the scheduling literature. Such graphs are sometimes obtained at compile time. 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 run time. We analyze the case where the task graph is a random out-tree. When the number of offspring of a task has a geometric distribution whose parameter is decreasing and convex in the level, then the breadth-first policy stochastically minimizes the makespan. If, however, this parameter is increasing and concave, then the depth-first policy stochastically minimizes the makespan.
29521719
Improving the Stability Characteristics of Asynchronous Traffic in FDDI Token Ring
The Fiber Distributed Data Interface (FDDI) token ring protocol supports two classes of traffic : synchronous and asynchronous. The time constraint mechanism of FDDI garantees the transmission delay of synchronous traffic. A Target Token Rotation Time (TTRT) being fixed, the FDDI protocol ensures that the token rotation time is always bounded above by twice TTRT. In this paper, we consider the stability issues of the asynchronous traffic in the FDDI protocol. We obtain sufficient and necessary stability conditions which indicates how the choice of TTRT affects the stability of the system. We suggest an improvement of the FDDI protocol for which the token rotation time is also bounded by twice TTRT. We show that the stability conditions of the new protocol are weaker (and thus it enables to transmit more asynchronous packets). This protocol is also easier to implement.
8080684
Well-Behaved Inference Rules for First-Order Theorem Proving
The concept of well-behaved inference rules is developed in first-order polynomial-based theorem proving. It is shown that well-behaved inference rules are complete for both the set of support strategy and the linear strategy. Furthermore, two concrete inference rules that are well behaved are presented, and two other strategies for them are described.
31153136
An Adaptive Scheduling Algorithm for Molecule Docking Design on Grid
Grid provides a promising platform for the efficient execution of drug molecular docking design. Scheduling such applications is challenging for the heterogeneity, autonomy, and dynamic adaptability of grid resources. Assuming resource owners have a preemptive priority, we propose an adaptive algorithm of jobs scheduling based on time balancing strategy, which solves parallel molecular docking task by using the idle resources in the Grid. A mathematical model is developed to predict performance, which also considers systems with heterogeneous machine utilization and heterogeneous service distribution. According to the time balancing policy, ligands are partitioned into several subtasks and scheduled. The expected value of molecular docking completion time is predicted with performance model. To get better parallel computing performance, an optimal subset of heterogeneous resources with the shortest parallel executing time of tasks can be selected with the algorithm.
2119274
Dynamical mobile terminal location registration in wireless PCS networks
In this paper, we propose a mobile terminal (MT) location registration/update model. In this model, the registration decision is based on two factors-the time elapsed since last call arrival and the distance the MT has traveled since last registration. It is established that the optimal registration strategy can be represented by a curve. Only when the state of the system reaches this curve is a registration performed. In order for an MT to calculate its traveled distance, an interactive implementation scheme and a distance calculation algorithm are developed. When the call interarrival times are independent and geometrically distributed, the proposed model becomes a distance-based model and, in this case, the optimal registration strategy is of threshold structure. For the distance-based model, a single sample path-based ordinal optimization algorithm is devised. In this algorithm, without any knowledge about the system parameters, the MT observes the system state transitions, estimates the ordinal of a set of strategies, and updates the registration strategy adaptively. Since only a single sample path is used, this algorithm can be implemented online. Several numerical examples are provided to compare the proposed model and the existing ones.
14780024
Fuzzy causal networks: general model, inference, and convergence
In this paper, we first propose a general framework for fuzzy causal networks (FCNs). Then, we study the dynamics and convergence of such general FCNs. We prove that any general FCN with constant weight matrix converges to a limit cycle or a static state, or the trajectory of the FCN is not repetitive. We also prove that under certain conditions a discrete state general FCN converges to its limit cycle or static state in O(n) steps, where n is the number of vertices of the FCN. This is in striking contrast with the exponential running time 2/sup n/, which is accepted widely for classic FCNs.
16579361
A Theory of Reactive Components
We present a theory of reactive components. We identify a component by its provided services, and specify the individual services by a guarded-design, which enables one to separate the responsibility of clients from the commitment made by the component, and model the behaviour of a component by a set of failures and divergences. Protocols are introduced to coordinate the interactions between a component and its environment. We adopt the notion of process refinement to formalise the substitutivity of components, and provide a complete proof method based on the notion of simulations. We also study the algebraic properties of component combinators.