A robust tri-state election algorithm for scalable applications

Existing election algorithms suffer limited scalability. This limit stems from the communication design which in turn stems from their fundamentally two-state behaviour. This paper presents a new election algorithm specifically designed to be highly scalable in broadcast networks whilst allowing any processing node to become coordinator with initially equal probability. To achieve this, careful attention has been paid to the communication design, and an additional state has been introduced. The design of the tri-state election algorithm has been motivated by the requirements analysis of a major research project to deliver robust scalable distributed applications, including load sharing, in hostile computing environments in which it is common for processing nodes to be rebooted frequently without notice. The new election algorithm is based in-part on a simple 'emergent' design. The science of emergence is of great relevance to developers of distributed applications because it describes how higher-level self-regulatory behaviour can arise from many participants following a small set of simple rules. The tri-state election algorithm is shown to have very low communication complexity in which the number of messages generated remains loosely-bounded regardless of scale for large systems; is highly scalable because nodes in the idle state do not transmit any messages; and because of its self-organising characteristics, is very stable.

A policy-definition language and prototype implementation library for policy-based autonomic systems

This paper presents work towards generic policy toolkit support for autonomic computing systems in which the policies themselves can be adapted dynamically and automatically. The work is motivated by three needs: the need for longer-term policy-based adaptation where the policy itself is dynamically adapted to continually maintain or improve its effectiveness despite changing environmental conditions; the need to enable non autonomics-expert practitioners to embed self-managing behaviours with low cost and risk; and the need for adaptive policy mechanisms that are easy to deploy into legacy code. A policy definition language is presented; designed to permit powerful expression of self-managing behaviours. The language is very flexible through the use of simple yet expressive syntax and semantics, and facilitates a very diverse policy behaviour space through both hierarchical and recursive uses of language elements. A prototype library implementation of the policy support mechanisms is described. The library reads and writes policies in well-formed XML script. The implementation extends the state of the art in policy-based autonomics through innovations which include support for multiple policy versions of a given policy type, multiple configuration templates, and meta-policies to dynamically select between policy instances and templates. Most significantly, the scheme supports hot-swapping between policy instances. To illustrate the feasibility and generalised applicability of these tools, two dissimilar example deployment scenarios are examined. The first is taken from an exploratory implementation of self-managing parallel processing, and is used to demonstrate the simple and efficient use of the tools. The second example demonstrates more-advanced functionality, in the context of an envisioned multi-policy stock trading scheme which is sensitive to environmental volatility

Flexible self-adjustment of task deployment in dynamic environments

This paper presents an investigation into dynamic self-adjustment of task deployment and other aspects of self-management, through the embedding of multiple policies. Non-dedicated loosely-coupled computing environments, such as clusters and grids are increasingly popular platforms for parallel processing. These abundant systems are highly dynamic environments in which many sources of variability affect the run-time efficiency of tasks. The dynamism is exacerbated by the incorporation of mobile devices and wireless communication. This paper proposes an adaptive strategy for the flexible run-time deployment of tasks; to continuously maintain efficiency despite the environmental variability. The strategy centres on policy-based scheduling which is informed by contextual and environmental inputs such as variance in the round-trip communication time between a client and its workers and the effective processing performance of each worker. A self-management framework has been implemented for evaluation purposes. The framework integrates several policy-controlled, adaptive services with the application code, enabling the run-time behaviour to be adapted to contextual and environmental conditions. Using this framework, an exemplar self-managing parallel application is implemented and used to investigate the extent of the benefits of the strategy

Computational modelling of multi-physics and multi-scale processes in parallel

This paper provides an overview of the developing needs for simulation software technologies for the computational modelling of problems that involve combinations of interactions amongst varying physical phenomena over a variety of time and space scales. Computational modelling of such problems requires software tech1nologies that enable the mathematical description of the interacting physical phenomena together with the solution of the resulting suites of equations in a numerically consistent and compatible manner. This functionality requires the structuring of simulation modules for specific physical phenomena so that the coupling can be effectively represented. These multi-physics and multi-scale computations are very compute intensive and the simulation software must operate effectively in parallel if it is to be used in this context. An approach to these classes of multi-disciplinary simulation in parallel is described, with some key examples of application to2 challenging engineering problems.

Matching search in fractal video compression and its parallel implementation in distributed computing environments

Fractal video compression is a relatively new video compression method. Its attraction is due to the high compression ratio and the simple decompression algorithm. But its computational complexity is high and as a result parallel algorithms on high performance machines become one way out. In this study we partition the matching search, which occupies the majority of the work in a fractal video compression process, into small tasks and implement them in two distributed computing environments, one using DCOM and the other using .NET Remoting technology, based on a local area network consists of loosely coupled PCs. Experimental results show that the parallel algorithm is able to achieve a high speedup in these distributed environments.

Multiphysics simulation of microwave curing in micro-electronics packaging applications

Purpose – This paper aims to present an open-ended microwave curing system for microelectronics components and a numerical analysis framework for virtual testing and prototyping of the system, enabling design of physical prototypes to be optimized, expediting the development process. Design/methodology/approach – An open-ended microwave oven system able to enhance the cure process for thermosetting polymer materials utilised in microelectronics applications is presented. The system is designed to be mounted on a precision placement machine enabling curing of individual components on a circuit board. The design of the system allows the heating pattern and heating rate to be carefully controlled optimising cure rate and cure quality. A multi-physics analysis approach has been adopted to form a numerical model capable of capturing the complex coupling that exists between physical processes. Electromagnetic analysis has been performed using a Yee finite-difference time-domain scheme, while an unstructured finite volume method has been utilized to perform thermophysical analysis. The two solvers are coupled using a sampling-based cross-mapping algorithm. Findings – The numerical results obtained demonstrate that the numerical model is able to obtain solutions for distribution of temperature, rate of cure, degree of cure and thermally induced stresses within an idealised polymer load heated by the proposed microwave system. Research limitations/implications – The work is limited by the absence of experimentally derived material property data and comparative experimental results. However, the model demonstrates that the proposed microwave system would seem to be a feasible method of expediting the cure rate of polymer materials. Originality/value – The findings of this paper will help to provide an understanding of the behaviour of thermosetting polymer materials during microwave cure processing.

Design of parallel algorithms for fractal video compression

The intrinsic independent features of the optimal codebook cubes searching process in fractal video compression systems are examined and exploited. The design of a suitable parallel algorithm reflecting the concept is presented. The Message Passing Interface (MPI) is chosen to be the communication tool for the implementation of the parallel algorithm on distributed memory parallel computers. Experimental results show that the parallel algorithm is able to reduce the compression time and achieve a high speed-up without changing the compression ratio and the quality of the decompressed image. A scalability test was also performed, and the results show that this parallel algorithm is scalable.

Parallel genetic algorithms for the solution of inverse heat conduction problems

A parallel genetic algorithm (PGA) is proposed for the solution of two-dimensional inverse heat conduction problems involving unknown thermophysical material properties. Experimental results show that the proposed PGA is a feasible and effective optimization tool for inverse heat conduction problems

Grey video compression methods using fractals

The authors' experience in the treatment of grey video compression using fractals is summarized and compared with other research in the same field. Experience with parallel and distributed computing is also discussed.

Modelling the reliability of components on flexible substrates

The use of flexible substrates is growing in many applications such as computer peripherals, hand held devices, telecommunications, automotive, aerospace, etc. The drive to adopt flexible circuits is due to their ability to reduce size, weight, assembly time and cost of final product. they also accommodate flexibility by allowing relative movement between component parts and provide a route for three dimensional packaging. This paper will describe some of the current research results from the Flex-No-Lead project, European Commission sponsored programme. The principle aim of this project is to investigate the processing, performance and reliability of flexible substrates when subjected to new environmentally friendly, lead-free soldering technologies. This paper will discuss the impact of specific design variables on performance and reliability. In particular the paper will focus on copper track designs, substrate material, dielectric material and solder mask defined joints

Research and design challenges for developing personalised eLearning systems

While E-learning technologies are continuously developing, there are number of emerging issues and challenges that have significant impact on e-learning research and design. These include educational, technological, sociological, and psychological viewpoints. The extant literature points out that a large number of existing E-learning systems have problems with offering reusable, personalized and learner-centric content. While developers are placing emphasis on the technology aspects of e-learning, critical conceptual and pedagogical issues are often ignored. This paper will reports on our research in design and development of personalised e-learning systems and some of the challenges and issues faced.

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

Schedules with due-date assignment and position-dependent processing times

Single machine scheduling problems are considered, in which the processing of jobs depend on positions of the jobs in a schedule and the due-dates are assigned either according to the CON rule (a due-date common to all jobs is chosen) or according to the SLK rule (the due-dates are computed by increasing the actual processing times of each job by a slack, common to all jobs). Polynomial-time dynamic programming algorithms are proposed for the problems with the objective functions that include the cost of assigning the due-dates, the total cost of disgarded jobs (which are not scheduled) and, possibly, the total earliness of the scheduled jobs.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Transporting jobs through a two-machine open shop

We consider the two-machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a 7/5-approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009