Parallel dynamic graph-partitioning for unstructured meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimization technique known as relative gain optimization which both balances the workload and attempts to minimize the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

An automatable generic strategy for dynamic load balancing in parallel structured mesh CFD codes

Parallel computing is now widely used in numerical simulation, particularly for application codes based on finite difference and finite element methods. A popular and successful technique employed to parallelize such codes onto large distributed memory systems is to partition the mesh into sub-domains that are then allocated to processors. The code then executes in parallel, using the SPMD methodology, with message passing for inter-processor interactions. In order to improve the parallel efficiency of an imbalanced structured mesh CFD code, a new dynamic load balancing (DLB) strategy has been developed in which the processor partition range limits of just one of the partitioned dimensions uses non-coincidental limits, as opposed to coincidental limits. The ‘local’ partition limit change allows greater flexibility in obtaining a balanced load distribution, as the workload increase, or decrease, on a processor is no longer restricted by the ‘global’ (coincidental) limit change. The automatic implementation of this generic DLB strategy within an existing parallel code is presented in this chapter, along with some preliminary results.

Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m⩾2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation.

Markovian bulk-arriving queues with state-dependent control at idle time

This paper considers a Markovian bulk-arriving queue modified to allow both mass arrivals when the queue is idle and mass departures which allow for the possibility of removing the entire workload. Properties of queues which terminate when the server becomes idle are developed first, since these play a key role in later developments. Results for the case of mass arrivals, but no mass annihilation, are then constructed with specific attention being paid to recurrence properties, equilibrium queue-size structure, and waiting-time distribution. A closed-form expression for the expected queue size and its Laplace transform are also established. All of these results are then generalised to allow for the removal of the entire workload, with closed-form expressions being developed for the equilibrium size and waiting-time distributions.

Simulating the evacuation of very large populations in large domains using a parallel implementation of the buildingEXODUS evacuation model

Computer egress simulation has potential to be used in large scale incidents to provide live advice to incident commanders. While there are many considerations which must be taken into account when applying such models to live incidents, one of the first concerns the computational speed of simulations. No matter how important the insight provided by the simulation, numerical hindsight will not prove useful to an incident commander. Thus for this type of application to be useful, it is essential that the simulation can be run many times faster than real time. Parallel processing is a method of reducing run times for very large computational simulations by distributing the workload amongst a number of CPUs. In this paper we examine the development of a parallel version of the buildingEXODUS software. The parallel strategy implemented is based on a systematic partitioning of the problem domain onto an arbitrary number of sub-domains. Each sub-domain is computed on a separate processor and runs its own copy of the EXODUS code. The software has been designed to work on typical office based networked PCs but will also function on a Windows based cluster. Two evaluation scenarios using the parallel implementation of EXODUS are described; a large open area and a 50 story high-rise building scenario. Speed-ups of up to 3.7 are achieved using up to six computers, with high-rise building evacuation simulation achieving run times of 6.4 times faster than real time.

The influence of crank configuration on muscle activity and torque production during arm crank ergometry

This study investigated the effect of crank configuration on muscle activity and torque production during submaximal arm crank ergometry. Thirteen non-specifically trained male participants volunteered. During the research trials they completed a warm-up at 15 W before two 3-min exercise stages were completed at 50 and 100 W; subjects used either a synchronous or asynchronous pattern of cranking. During the final 30-s of each submaximal exercise stage electromyographic and torque production data were collected. After the data had been processed each parameter was analysed using separate 2-way ANOVA tests with repeated measures. The activity of all muscles increased in line with external workload, although a shift in the temporal pattern of muscle activity was noted between crank configurations. Patterns of torque production during asynchronous and synchronous cranking were distinct. Furthermore, peak, minimum and delta (peak-minimum) torque values were different (P < 0.05) between crank configurations at both workloads. For example, at 100 W, peak torque using synchronous [19.6 (4.3) Nm] cranking was higher (P < 0.05) compared to asynchronous [16.8 (1.6) Nm] cranking. In contrast minimum torque was lower (P < 0.05) at 100 W using synchronous [4.8 (1.7) Nm] compared to asynchronous [7.3 (1.2) Nm] cranking. There was a distinct bilateral asymmetry in torque production during asynchronous cranking with the dominant transmitting significantly more force to the crank arm. Taken together, these preliminary data demonstrate the complex nature of muscle activity during arm crank ergometry performed with an asynchronous or synchronous crank set-up. Further work is required to determine how muscle activity (EMG activity) and associated patterns of torque production influence physiological responses and functional capacity during arm crank ergometry.

Workplace violence and intentions to quit: results from a survey of London nurses

Study Objective: Work-place violence, harassment and abuse is an increasing feature of nurses’ experience of work in many countries. There is some evidence that the experience of workplace violence affects levels of job satisfaction (Hesketh et al 2003) and career decisions (e.g. Mayer et al 1999, Fernandes et al 1999). This paper reports on verbal and physical abuse by patients, relatives and carers, as well as racial and sexual harassment in Acute Hospitals in London and investigates whether workplace violence affects nurses’ intentions to leave either their current job or the nursing profession, controlling for a number of other factors that are known to affect career decisions, such as workload, pay and own health. Method: A questionnaire designed by two of the authors (Reeves and West) to assess many different aspects of nurses work life was used in a postal survey of nurses grades A to I practising in twenty London acute trusts in 2002. A total of 6,160 clinical nurses were mailed the questionnaires and 2,880 returned completed questionnaires, resulting in an overall response rate of 47%, discounting undelivered questionnaires. Respondents worked in a wide variety of clinical settings but mainly in acute medical and surgical wards. In addition to descriptive statistics, results were analysed using logistic regression with robust standard errors: the appropriate test when the dependent variable is dichotomous and the individual respondents clustered within units (nurses working within hospitals are not statistically independent). Results: Our results show high levels of racial (%), sexual (%) and other, unspecified forms of harassment (%), as well as verbal and physical abuse (14% had been physically assaulted with 5% being assaulted more than once), over the previous 6 months. A very small number (1%) reported experiencing all three forms of harassment; 12% two forms and 29% one form. Only 45% of this sample intended to stay in nursing for at least 3 years; 40% were undecided and 15% intended to leave. Logistic regression estimates showed that reported levels of abuse and harassment had a significant impact on respondents’ career intentions, even in models that controlled for known factors affecting career decisions. About 70% of our respondents reported that they had had too little training in dealing with aggressive behaviour—or none at all—but there was no statistical relationship between lack of training and reported assaults. Conclusions: The international shortage of health care workers is due at least in part to low retention rates. It is crucial to investigate nurses’ experiences of work to identify the factors that shape their career decisions. Workplace violence is increasingly acknowledged as an international, service-wide, health care problem. This paper adds to the literature that shows that workplace violence has an impact on nurses’ career decisions. The implications for managers and policy makers are that strengthening systems of security and providing nurses with training in interpersonal relationships including dealing with aggressive patients could slow nurse turnover.

The impact of the nursing workforce on patient outcomes in intensive care

Introduction: Evidence from studies conducted mainly in the US and mainland Europe suggests that characteristics of the workforce, such as nurse patient ratios and workload (measured in a number of different ways) may be linked to variations in patient outcomes across health care settings (Carmel and Rowan 2001). Few studies have tested this relationship in the UK thus questions remain about whether we are justified in extrapolating evidence from studies conducted in very different health care systems. Objectives: To investigate whether characteristics of the nursing workforce affect patient mortality UK Intensive Care Units. Data: Patient data came from the case mix programme, Intensive Care National Audit and Research Centre (ICNARC), while information about the units came from a survey of all ICUs in England (Audit Comission 1998). The merged data set contained information on 43,859 patients in 69 units across England. ICNARC also supplied a risk adjustment variable to control for patient characteristics that are often the most important determinants of survival. Methods: Multivariate multilevel logistic regression. Findings: Higher numbers of direct care nurses and lower scores on measures of workload(proportion of occupied beds at the time the patient was admitted and mean daily transfers into the unit) were associated with lower mortality rates. Furthermore, the effect of the number of direct care nurses was greatest on the life chances of the patients who were most at risk of dying. Implications: This study has wide implications for workforce policy and planning because it shows that the size of the nursing workforce is associated with mortality (West et al 2006). Few studies have demonstrated this relationship in the UK. This study has a number of strengths and weaknesses and further research is required to determine whether this relationship between the nursing workforce and patient outcomes is causal.

Parallel dynamic load-balancing for adaptive unstructured meshes

This chapter describes a parallel optimization technique that incorporates a distributed load-balancing algorithm and provides an extremely fast solution to the problem of load-balancing adaptive unstructured meshes. Moreover, a parallel graph contraction technique can be employed to enhance the partition quality and the resulting strategy outperforms or matches results from existing state-of-the-art static mesh partitioning algorithms. The strategy can also be applied to static partitioning problems. Dynamic procedures have been found to be much faster than static techniques, to provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data. The method employs a new iterative optimization technique that balances the workload and attempts to minimize the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more quickly. The dynamic evolution of load has three major influences on possible partitioning techniques; cost, reuse, and parallelism. The unstructured mesh may be modified every few time-steps and so the load-balancing must have a low cost relative to that of the solution algorithm in between remeshing.

Dynamic load-balancing for parallel adaptive unstructured meshes

A parallel method for dynamic partitioning of unstructured meshes is described. The method employs a new iterative optimisation technique which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more quickly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Parallel partitioning of unstructured meshes

A method is outlined for optimising graph partitions which arise in mapping un- structured mesh calculations to parallel computers. The method employs a combination of iterative techniques to both evenly balance the workload and minimise the number and volume of interprocessor communications. They are designed to work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. The algorithms can also be used for dynamic load-balancing and a clustering technique can additionally be employed to speed up the whole process. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds.

Dynamic load balancing of distributed memory parallel computational mechanics using unstructured meshes for multi-physical modelling

As the complexity of parallel applications increase, the performance limitations resulting from computational load imbalance become dominant. Mapping the problem space to the processors in a parallel machine in a manner that balances the workload of each processors will typically reduce the run-time. In many cases the computation time required for a given calculation cannot be predetermined even at run-time and so static partition of the problem returns poor performance. For problems in which the computational load across the discretisation is dynamic and inhomogeneous, for example multi-physics problems involving fluid and solid mechanics with phase changes, the workload for a static subdomain will change over the course of a computation and cannot be estimated beforehand. For such applications the mapping of loads to process is required to change dynamically, at run-time in order to maintain reasonable efficiency. The issue of dynamic load balancing are examined in the context of PHYSICA, a three dimensional unstructured mesh multi-physics continuum mechanics computational modelling code.

Mesh partitioning and load balancing for distributed memory parallel systems

A method is outlined for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a relative gain iterative technique to both evenly balance the workload and minimise the number and volume of interprocessor communications. A parallel graph reduction technique is also briefly described and can be used to give a global perspective to the optimisation. The algorithms work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds. The algorithms can also be used for dynamic load-balancing, reusing existing partitions and in this case the procedures are much faster than static techniques, provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data.

Parallel dynamic graph-partitioning for unstructured meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimisation technique known as relative gain optimisation which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.