ELISA: An Estimated Load Information Scheduling Algorithm for Distributed Computing Systems

In this paper, we present a decentralized dynamic load scheduling/balancing algorithm called ELISA (Estimated Load Information Scheduling Algorithm) for general purpose distributed computing systems. ELISA uses estimated state information based upon periodic exchange of exact state information between neighbouring nodes to perform load scheduling. The primary objective of the algorithm is to cut down on the communication and load transfer overheads by minimizing the frequency of status exchange and by restricting the load transfer and status exchange within the buddy set of a processor. It is shown that the resulting algorithm performs almost as well as a perfect information algorithm and is superior to other load balancing schemes based on the random sharing and Ni-Hwang algorithms. A sensitivity analysis to study the effect of various design parameters on the effectiveness of load balancing is also carried out. Finally, the algorithm's performance is tested on large dimensional hypercubes in the presence of time-varying load arrival process and is shown to perform well in comparison to other algorithms. This makes ELISA a viable and implementable load balancing algorithm for use in general purpose distributed computing systems.

Improving spoken term detection using complementary information

This research has made contributions to the area of spoken term detection (STD), defined as the process of finding all occurrences of a specified search term in a large collection of speech segments. The use of visual information in the form of lip movements of the speaker in addition to audio and the use of topic of the speech segments, and the expected frequency of words in the target speech domain, are proposed. By using these complementary information, improvement in the performance of STD has been achieved which enables efficient search of key words in large collection of multimedia documents.

Architecture Optimization of Aerospace Computing Systems

Simultaneous consideration of both performance and reliability issues is important in the choice of computer architectures for real-time aerospace applications. One of the requirements for such a fault-tolerant computer system is the characteristic of graceful degradation. A shared and replicated resources computing system represents such an architecture. In this paper, a combinatorial model is used for the evaluation of the instruction execution rate of a degradable, replicated resources computing system such as a modular multiprocessor system. Next, a method is presented to evaluate the computation reliability of such a system utilizing a reliability graph model and the instruction execution rate. Finally, this computation reliability measure, which simultaneously describes both performance and reliability, is applied as a constraint in an architecture optimization model for such computing systems. Index Terms-Architecture optimization, computation

Byzantine-resilient distributed computing systems

This paper is aimed at reviewing the notion of Byzantine-resilient distributed computing systems, the relevant protocols and their possible applications as reported in the literature. The three agreement problems, namely, the consensus problem, the interactive consistency problem, and the generals problem have been discussed. Various agreement protocols for the Byzantine generals problem have been summarized in terms of their performance and level of fault-tolerance. The three classes of Byzantine agreement protocols discussed are the deterministic, randomized, and approximate agreement protocols. Finally, application of the Byzantine agreement protocols to clock synchronization is highlighted.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Towards formal specification of a distributed computing system

Onboard spacecraft computing system is a case of a functionally distributed system that requires continuous interaction among the nodes to control the operations at different nodes. A simple and reliable protocol is desired for such an application. This paper discusses a formal approach to specify the computing system with respect to some important issues encountered in the design and development of a protocol for the onboard distributed system. The issues considered in this paper are concurrency, exclusiveness and sequencing relationships among the various processes at different nodes. A 6-tuple model is developed for the precise specification of the system. The model also enables us to check the consistency of specification and deadlock caused due to improper specification. An example is given to illustrate the use of the proposed methodology for a typical spacecraft configuration. Although the theory is motivated by a specific application the same may be applied to other distributed computing system such as those encountered in process control industries, power plant control and other similar environments.

Implementation of parallel tridiagonal solvers for a heterogeneous computing environment

Tridiagonal diagonally dominant linear systems arise in many scientific and engineering applications. The standard Thomas algorithm for solving such systems is inherently serial forming a bottleneck in computation. Algorithms such as cyclic reduction and SPIKE reduce a single large tridiagonal system into multiple small independent systems which can be solved in parallel. We have developed portable cyclic reduction and SPIKE algorithm OpenCL implementations with the intent to target a range of co-processors in a heterogeneous computing environment including Field Programmable Gate Arrays (FPGAs), Graphics Processing Units (GPUs) and other multi-core processors. In this paper, we evaluate these designs in the context of solver performance, resource efficiency and numerical accuracy.

Structural effects of a dimer interface mutation on catalytic activity of triosephosphate isomerase.The role of conserved residues and complementary mutations

The active site of triosephosphate isomerase (TIM, EC: 5.3.1.1), a dimeric enzyme, lies very close to the subunit interface. Attempts to engineer monomeric enzymes have yielded well-folded proteins with dramatically reduced activity. The role of dimer interface residues in the stability and activity of the Plasmodium falciparum enzyme, PfTIM, has been probed by analysis of mutational effects at residue 74. The PfTIM triple mutant W11F/W168F/Y74W (Y74W*) has been shown to dissociate at low protein concentrations, and exhibits considerably reduced stability in the presence of denaturants, urea and guanidinium chloride. The Y74W* mutant exhibits concentration-dependent activity, with an approximately 22-fold enhancement of kcat over a concentration range of 2.5–40 μm, suggesting that dimerization is obligatory for enzyme activity. The Y74W* mutant shows an approximately 20-fold reduction in activity compared to the control enzyme (PfTIM WT*, W11F/W168F). Careful inspection of the available crystal structures of the enzyme, together with 412 unique protein sequences, revealed the importance of conserved residues in the vicinity of the active site that serve to position the functional K12 residue. The network of key interactions spans the interacting subunits. The Y74W* mutation can perturb orientations of the active site residues, due to steric clashes with proximal aromatic residues in PfTIM. The available crystal structures of the enzyme from Giardia lamblia, which contains a Trp residue at the structurally equivalent position, establishes the need for complementary mutations and maintenance of weak interactions in order to accommodate the bulky side chain and preserve active site integrity.

Use of a volatile buffer at ambient temperature *1: Versatile approach to the purification of self-complementary synthetic deoxyoligonucleotides by reversed-phase high-performance liquid chromatography

Abstract is not available.

BSDD-2.0: Biomolecules Segment Display Device - An updated web accessible computing resource

The existing internet computing resource, Biomolecules Segment Display Device (BSDD), has been updated with several additional useful features. An advanced option is provided to superpose the structural motifs obtained from a search on the Protein Data Bank (PDB) in order to see if the three-dimensional structures adopted by identical or similar sequence motifs are the same. Furthermore, the options to display structural aspects like inter- and intra-molecular interactions, ion-pairs, disulphide bonds, etc. have been provided.The updated resource is interfaced with an up-to-date copy of the public domain PDB as well as 25 and 90% non-redundant protein structures. Further, users can upload the three-dimensional atomic coordinates (PDB format) from the client machine. A free molecular graphics program, JMol, is interfaced with it to display the three-dimensional structures.

Phased-Mission Analysis for Evaluating the Effectiveness of Aerospace Computing-Systems

Effectiveness evaluation of aerospace fault-tolerant computing systems used in a phased-mission environment is rather tricky and difficult because of the interaction of its several degraded performance levels with the multiple objectives of the mission and the use environment. Part I uses an approach based on multiobjective phased-mission analysis to evaluate the effectiveness of a distributed avionics architecture used in a transport aircraft. Part II views the computing system as a multistate s-coherent structure. Lower bounds on the probabilities of accomplishing various levels of performance are evaluated.

Data distribution and task scheduling for distributed computing of all-to-all comparison problems

This research studied distributed computing of all-to-all comparison problems with big data sets. The thesis formalised the problem, and developed a high-performance and scalable computing framework with a programming model, data distribution strategies and task scheduling policies to solve the problem. The study considered storage usage, data locality and load balancing for performance improvement in solving the problem. The research outcomes can be applied in bioinformatics, biometrics and data mining and other domains in which all-to-all comparisons are a typical computing pattern.

Complementary forages – integration at a whole-farm level

A high proportion of the Australian and New Zealand dairy industry is based on a relatively simple, low input and low cost pasture feedbase. These factors enable this type of production system to remain internationally competitive. However, a key limitation of pasture-based dairy systems is periodic imbalances between herd intake requirements and pasture DM production, caused by strong seasonality and high inter-annual variation in feed supply. This disparity can be moderated to a certain degree through the strategic management of the herd through altering calving dates and stocking rates, and the feedbase by conserving excess forage and irrigating to flatten seasonal forage availability. Australasian dairy systems are experiencing emerging market and environmental challenges, which includes increased competition for land and water resources, decreasing terms of trade, a changing and variable climate, an increasing environmental focus that requires improved nutrient and water-use efficiency and lower greenhouse gas emissions. The integration of complementary forages has long been viewed as a means to manipulate the home-grown feed supply, to improve the nutritive value and DM intake of the diet, and to increase the efficiency of inputs utilised. Only recently has integrating complementary forages at the whole-farm system level received the significant attention and investment required to examine their potential benefit. Recent whole-of-farm research undertaken in both Australia and New Zealand has highlighted the importance of understanding the challenges of the current feedbase and the level of complementarity between forage types required to improve profit, manage risk and/or alleviate/mitigate against adverse outcomes. This paper reviews the most recent systems-level research into complementary forages, discusses approaches to modelling their integration at the whole-farm level and highlights the potential of complementary forages to address the major challenges currently facing pasture-based dairy systems.

Ant colony optimization for reporting cell planning in mobile computing using selective paging strategy

Location management problem that arise in mobile computing networks is addressed. One method used in location management is to designate sonic of the cells in the network as "reporting cells". The other cells in the network are "non-reporting cells". Finding an optimal set of reporting cells (or reporting cell configuration) for a given network. is a difficult combinatorial optimization problem. In fact this is shown to be an NP-complete problem. in an earlier study. In this paper, we use the selective paging strategy and use an ant colony optimization method to obtain the best/optimal set of reporting cells for a given a network.