Design and Performance Analysis of Divisible Load Scheduling Strategies on Arbitrary Graphs

In this paper, we consider the problem of scheduling divisible loads on arbitrary graphs with the objective to minimize the total processing time of the entire load submitted for processing. We consider an arbitrary graph network comprising heterogeneous processors interconnected via heterogeneous links in an arbitrary fashion. The divisible load is assumed to originate at any processor in the network. We transform the problem into a multi-level unbalanced tree network and schedule the divisible load. We design systematic procedures to identify and eliminate any redundant processor–link pairs (those pairs whose consideration in scheduling will penalize the performance) and derive an optimal tree structure to obtain an optimal processing time, for a fixed sequence of load distribution. Since the algorithm thrives to determine an equivalent number of processors (resources) that can be used for processing the entire load, we refer to this approach as resource-aware optimal load distribution (RAOLD) algorithm. We extend our study by applying the optimal sequencing theorem proposed for single-level tree networks in the literature for multi-level tree for obtaining an optimal solution. We evaluate the performance for a wide range of arbitrary graphs with varying connectivity probabilities and processor densities. We also study the effect of network scalability and connectivity. We demonstrate the time performance when the point of load origination differs in the network and highlight certain key features that may be useful for algorithm and/or network system designers. We evaluate the time performance with rigorous simulation experiments under different system parameters for the ease of a complete understanding.     

A Novel Optimal Load Distribution Algorithm for Divisible Loads

A new model for divisible load problem is introduced. Its characteristics are analyzed. Optimal load distribution algorithms on the new model are presented for the tree-network and linear network. Applications that fit our model are briefly described. We show that our model outperforms the existing model such as Cheng–Robertazzi model. We show that the linear model is equivalent to a single-level tree network if the intermediate processors do not follow the store-and-forward communication model, but they follow the store-and-bypass model. This paper introduces the concept of store-and-bypass for divisible load theory.     

A Multistage Load Distribution Strategy for Three-Dimensional Meshes

We study the problem of scheduling a divisible load in a three-dimensional mesh of processors. The objective is to find partition of a load into shares and distribution of load shares among processors which minimize load processing time subject to communication delays involved in sending load from one processor to another. We propose a new scheduling algorithm which distributes load in a sequence of stages across the network, each stage brings load to a set of processors located at the same distance from the load source. A key feature of our solution is that sets of processors receive load in the order of decreasing processing capacities. We call this scheduling strategy Largest Layer First. A theorem about the processing time attained by the algorithm is stated. Performance of the algorithm is compared to earlier results.     

Self-sustained Oscillations in Blood Flow Through a Honeycomb Capillary Network

Numerical simulations of unsteady blood flow through a honeycomb network originating at multiple inlets and terminating at multiple outlets are presented and discussed under the assumption that blood behaves as a continuum with variable constitution. Unlike a tree network, the honeycomb network exhibits both diverging and converging bifurcations between branching capillary segments. Numerical results based on a finite difference method demonstrate that as in the case of tree networks considered in previous studies, the cell partitioning law at diverging bifurcations is an important parameter in both steady and unsteady flow. Specifically, a steady flow may spontaneously develop self-sustained oscillations at critical conditions by way of a Hopf bifurcation. Contrary to tree-like networks comprised entirely of diverging bifurcations, the critical parameters for instability in honeycomb networks depend weakly on the system size. The blockage of one or more network segments due to the presence of large cells or the occurrence of capillary constriction may cause flow reversal or trigger a transition to unsteady flow.     

Phylogenetic Reconstruction Using an Unsupervised Growing Neural Network That Adopts the Topology of a Phylogenetic Tree

We propose a new type of unsupervised, growing, self-organizing neural network that expands itself by following the taxonomic relationships that exist among the sequences being classified. The binary tree topology of this neutral network, contrary to other more classical neural network topologies, permits an efficient classification of sequences. The growing nature of this procedure allows to stop it at the desired taxonomic level without the necessity of waiting until a complete phylogenetic tree is produced. This novel approach presents a number of other interesting properties, such as a time for convergence which is, approximately, a lineal function of the number of sequences. Computer simulation and a real example show that the algorithm accurately finds the phylogenetic tree that relates the data. All this makes the neural network presented here an excellent tool for phylogenetic analysis of a large number of sequences. Received: 14 May 1996 / Accepted: 6 August 1996     

Network Based Prediction Model for Genomics Data Analysis

Biological networks, such as genetic regulatory networks and protein interaction networks, provide important information for studying gene/protein activities. In this paper, we propose a new method, NetBoosting, for incorporating a priori biological network information in analyzing high dimensional genomics data. Specially, we are interested in constructing prediction models for disease phenotypes of interest based on genomics data, and at the same time identifying disease susceptible genes. We employ the gradient descent boosting procedure to build an additive tree model and propose a new algorithm to utilize the network structure in fitting small tree weak learners. We illustrate by simulation studies and a real data example that, by making use of the network information, NetBoosting outperforms a few existing methods in terms of accuracy of prediction and variable selection.     

Contention-Aware Communication Schedule for High-Speed Communication

A lot of efforts have been devoted to address the software overhead problem in the past decade, which is known as the major hindrance on high-speed communication. However, this paper shows that having a low-latency communication system does not guarantee to achieve high performance, as there are other communication issues that have not been fully addressed by the use of low-latency communication, such as contention and scheduling of communication events. In this paper, we use the complete exchange operation as a case study to show that with careful design of communication schedules, we can achieve efficient communication as well as prevent congestion. We have developed a complete exchange algorithm, the Synchronous Shuffle Exchange, which is an optimal algorithm on the non-blocking network. To avoid congestion loss caused by the non-deterministic delays in communication events, a global congestion control scheme is introduced. This scheme coordinates all participating nodes to monitor and regulate the traffic load, which effectively avoids congestion loss and maintains sufficient throughput to maximize the performance. To improve the effectiveness of the congestion control scheme when working on the hierarchical network, we incorporate information on the network topology to devise a contention-aware permutation. This permutation scheme generates a communication schedule, which is both node and switch contention-free as well as distributing the network loads more evenly across the hierarchy. This relieves the congestion build-up at the uplink ports and improves the synchronism of the traffic information exchange between cluster nodes. Performance results of our implementation on a 32-node cluster with various network configurations are examined and reported in this paper.     

Reconstructing the evolutionary history of polyploids from multilabeled trees

In recent studies, phylogenetic networks have been derived from so-called multilabeled trees in order to understand the origins of certain polyploids. Although the trees used in these studies were constructed using sophisticated techniques in phylogenetic analysis, the presented networks were inferred using ad hoc arguments that cannot be easily extended to larger, more complicated examples. In this paper, we present a general method for constructing such networks, which takes as input a multilabeled phylogenetic tree and outputs a phylogenetic network with certain desirable properties. To illustrate the applicability of our method, we discuss its use in reconstructing the evolutionary history of plant allopolyploids. We conclude with a discussion concerning possible future directions. The network construction method has been implemented and is freely available for use from http://www.uea.ac.uk/ approximately a043878/padre.html.     

Re-Evaluation of the AASHTO-Flexible Pavement Design Equation with Neural Network Modeling

Here we establish that equivalent single-axle loads values can be estimated using artificial neural networks without the complex design equality of American Association of State Highway and Transportation Officials (AASHTO). More importantly, we find that the neural network model gives the coefficients to be able to obtain the actual load values using the AASHTO design values. Thus, those design traffic values that might result in deterioration can be better calculated using the neural networks model than with the AASHTO design equation. The artificial neural network method is used for this purpose. The existing AASHTO flexible pavement design equation does not currently predict the pavement performance of the strategic highway research program (Long Term Pavement Performance studies) test sections very accurately, and typically over-estimates the number of equivalent single axle loads needed to cause a measured loss of the present serviceability index. Here we aimed to demonstrate that the proposed neural network model can more accurately represent the loads values data, compared against the performance of the AASHTO formula. It is concluded that the neural network may be an appropriate tool for the development of databased-nonparametric models of pavement performance.     

Bayesian Neural Network Models for Censored Data

Neural networks are considered by many to be very promising tools for classification and prediction. The flexibility of the neural network models often result in over-fit. Shrinking the parameters using a penalized likelihood is often used in order to overcome such over-fit. In this paper we extend the approach proposed by FARAGGI and SIMON (1995a) to modeling censored survival data using the input-output relationship associated with a single hidden layer feed-forward neural network. Instead of estimating the neural network parameters using the method of maximum likelihood, we place normal prior distributions on the parameters and make inferences based on derived posterior distributions of the parameters. This Bayesian formulation will result in shrinking the parameters of the neural network model and will reduce the over-fit compared with the maximum likelihood estimators. We illustrate our proposed method on a simulated and a real example.     

Network analysis of an arterial tree

The arterial tree of a Sprague-Dawley rat was casted and carefully mapped with the aim of comparing its network characteristics with those suggested by the classical model of an arterial tree. It is shown that if the tree is to be measured accurately, the concept of 'whole vessels' on which the classical model is based must be abandoned since such vessels do not actually exist in the network, nor can they be accurately defined. The concept of 'vessel segments' is proposed instead and its use is demonstrated. A total of 1313 vessel segments in the arterial tree of the rat are mapped and divided into well defined 'levels'. The length and diameter of each segment are measured and the distribution and averages of these at different levels are presented as indicators of the branching characteristics of the tree.     

High-pass filtering of small signals by the rod network in the retina of the toad, Bufo marinus

The electrical spread of excitation in the network of rod photoreceptors was studied by intracellular recording in the isolated, perfused retina of the toad, Bufo marinus. Experiments with dim, bar-shaped flashes of light revealed that the rod network behaves as a high-pass filter to laterally propagating small signals. Such a behavior had been found earlier in the turtle (Detwiler et al., 1980). Three electrical equivalent circuit models that can explain this behavior were considered and analytical solutions to the network equations were obtained. By fitting these analytical expressions to linear responses elicited by weak light flashes and to voltage excursions elicited by extrinsic current injections, values for the circuit parameters were determined. Values obtained by independent methods were consistent. The effects of changing each of these parameters in turn upon the high-pass filtering of small signals were then predicted. These predictions provided a framework for an analysis of the ionic basis of the underlying mechanism, which is described in the following paper.     

Computational Rules for Chemotaxis in the Nematode C. elegans

We derive a linear neural network model of the chemotaxis control circuit in the nematode Caenorhabditis elegans and demonstrate that this model is capable of producing nematodelike chemotaxis. By expanding the analytic solution for the network output in time-derivatives of the network input, we extract simple computational rules that reveal how the model network controls chemotaxis. Based on these rules we find that optimized linear networks typically control chemotaxis by computing the first time-derivative of the chemical concentration and modulating the body turning rate in response to this derivative. We argue that this is consistent with behavioral studies and a plausible mechanism for at least one component of chemotaxis in real nematodes.     

Distinctive Network Topology of Phase-Separated Proteins in Human Interactome

Liquid-liquid phase separation (LLPS) is an important mechanism that mediates the formation of biomolecular condensates. Despite the immense interest in LLPS, phase-separated proteins verified by experiments are still limited, and identification of phase-separated proteins at proteome-scale is a challenging task. Multivalent interaction among macromolecules is the driving force of LLPS, which suggests that phase-separated proteins may harbor distinct biological characteristics in protein–protein interactions (PPIs). In this study, we constructed an integrated human PPI network (HPIN) and mapped phase-separated proteins into it. Analysis of the network parameters revealed differences of network topology between phase-separated proteins and others. The results further suggested the efficiency when applying topological similarities in distinguishing components of MLOs. Furthermore, we found that affinity purification mass spectrometry (AP-MS) detects PPIs more effectively than yeast-two hybrid system (Y2H) in phase separation-driven condensates. Our work provides the first global view of the distinct network topology of phase-separated proteins in human interactome, suggesting incorporation of PPI network for LLPS prediction in further studies.     

A new approach to the job scheduling problem in computational grids

Job scheduling is one of the most challenging issues in Grid resource management that strongly affects the performance of the whole Grid environment. The major drawback of the existing Grid scheduling algorithms is that they are unable to adapt with the dynamicity of the resources and the network conditions. Furthermore, the network model that is used for resource information aggregation in most scheduling methods is centralized or semi-centralized. Therefore, these methods do not scale well as Grid size grows and do not perform well as the environmental conditions change with time. This paper proposes a learning automata-based job scheduling algorithm for Grids. In this method, the workload that is placed on each Grid node is proportional to its computational capacity and varies with time according to the Grid constraints. The performance of the proposed algorithm is evaluated through conducting several simulation experiments under different Grid scenarios. The obtained results are compared with those of several existing methods. Numerical results confirm the superiority of the proposed algorithm over the others in terms of makespan, flowtime, and load balancing.     

A short-term temperature forecaster based on a novel radial basis functions neural network

Many applications dealing with electric load forecasting in buildings require temperature prediction. A new method for short-term temperature forecasting based on a Radial Basis Functions Neural Network, initialized by a Regression Tree, is presented. In this method, each terminal node of the tree contributes one hidden unit to the RBF network. The forecaster uses the current coded hour and the temperature as inputs, and predicts the next hour temperature. The results demonstrate this predictor can be used for load forecasting.     

Optimal, efficient reconstruction of phylogenetic networks with constrained recombination

A phylogenetic network is a generalization of a phylogenetic tree, allowing structural properties that are not tree-like. In a seminal paper, Wang et al.(1) studied the problem of constructing a phylogenetic network, allowing recombination between sequences, with the constraint that the resulting cycles must be disjoint. We call such a phylogenetic network a "galled-tree". They gave a polynomial-time algorithm that was intended to determine whether or not a set of sequences could be generated on galled-tree. Unfortunately, the algorithm by Wang et al.(1) is incomplete and does not constitute a necessary test for the existence of a galled-tree for the data. In this paper, we completely solve the problem. Moreover, we prove that if there is a galled-tree, then the one produced by our algorithm minimizes the number of recombinations over all phylogenetic networks for the data, even allowing multiple-crossover recombinations. We also prove that when there is a galled-tree for the data, the galled-tree minimizing the number of recombinations is "essentially unique". We also note two additional results: first, any set of sequences that can be derived on a galled tree can be derived on a true tree (without recombination cycles), where at most one back mutation per site is allowed; second, the site compatibility problem (which is NP-hard in general) can be solved in polynomial time for any set of sequences that can be derived on a galled tree. Perhaps more important than the specific results about galled-trees, we introduce an approach that can be used to study recombination in general phylogenetic networks. This paper greatly extends the conference version that appears in an earlier work.(8) PowerPoint slides of the conference talk can be found at our website.(7).     

Should artificial neural networks replace linear models in tree ring based climate reconstructions?

Studies focused on tree ring—climate relationships usually use linear methods to find the optimal transfer function. In our study, three sites with three different tree species from the Western Balkan region were selected to compare linear and artificial neural network (ANN) nonlinear models and to see whether linear models can be potentially replaced with ANN in climate reconstruction. For each site, one linear and two different ANN models were calculated. For all analysed sites, we were able to find a better fit using the advanced technique of ANN. All calibration and verification statistics were in favour of ANN models. A climate variable was reconstructed for a selected site using linear and nonlinear ANN methods. We demonstrated that ANN is always a more effective method, which always produce better results than linear models. The key to success is a properly selected training algorithm, which prevents overfitting and is able to find the optimal transfer function, also linear, if that is the case.     

On the interaction between roadrunner or railway scheduling and priority lists or resource flow networks

In previous research (Tian and Demeulemeester 2010), we have shown that in realistic situations railway scheduling improves both the stability and the expected project length over roadrunner scheduling. In this paper, we introduce the concept of resource flow networks in this analysis and determine what the impact of combining roadrunner or railway scheduling with priority lists or resource flow networks is on the average project length, the standard deviation of the project length, the timely project completion probability and the stability cost. Extensive computational results will be presented on both small and larger projects and a statistical analysis will be conducted by using SAS PROC GLM, indicating that in smaller projects the optimal combination strongly depends on the performance indicator of interest, while in larger projects a combination of roadrunner scheduling with a resource flow network seems optimal.