A message passing strategy for array redistributions in a torus network

The array redistribution problem occurs in many important applications in parallel computing. In this paper, we consider this problem in a torus network. Tori are preferred to other multidimensional networks (like hypercubes) due to their better scalability (IEE Trans. Parallel Distrib. Syst. 50(10), 1201–1218, [2001]). We present a message combining approach that splits any array redistribution problem in a series of broadcasts where all sources send messages of the same size, thus a balanced traffic load is achieved. Unlike existing array redistribution algorithms, the scheme introduced in this work eliminates the need for data reorganization in the memory of the source and target processors. Moreover, the processing of the scheduled broadcasts is pipelined, thus the total cost of redistribution is reduced.

A dominant predecessor duplication scheduling algorithm for heterogeneous systems

This paper proposes a new duplication-based task scheduling algorithm for distributed heterogeneous computing (DHC) systems. For such systems, many researchers have focused on solving the NP-complete problem of scheduling directed acyclic task graphs to minimize the makespan. However, the heterogeneity of computational resources and communication mechanisms poses some major obstacles to achieving high parallel efficiency. This paper proposes a heuristic strategy called the Dominant Predecessor Duplication (DPD) scheduling algorithm, which allows for system heterogeneities and communication bandwidth to exploit the potential of parallel processing. This algorithm can improve system utilization and avoid redundant resource consumption, resulting in better schedules. Experimental results show that the system heterogeneities and program structures of applications affect scheduling performance, and that our presented algorithm is better able to avoid these problems than those presented in previous literature. Here, we show that our algorithm can be applied to design efficient distributed systems to overcome performance bottlenecks caused by system heterogeneities.

Enabling scalable parallel implementations of structured adaptive mesh refinement applications

Parallel implementations of dynamic structured adaptive mesh refinement (SAMR) methods lead to significant runtime management challenges that can limit their scalability on large systems. This paper presents a runtime engine that addresses the scalability of SAMR applications with localized refinements and high SAMR efficiencies on large numbers of processors (upto 1024 processors). The SAMR runtime engine augments hierarchical partitioning with bin-packing based load-balancing to manage the space-time heterogeneity of the SAMR grid hierarchy, and includes a communication substrate that optimizes the use of MPI non-blocking communication primitives. An experimental evaluation on the IBM SP2 supercomputer using the 3-D Richtmyer-Meshkov compressible turbulence kernel demonstrates the effectiveness of the runtime engine in improving SAMR scalability.

COMUNICAR: designing a multimedia, context-aware human-machine interface for cars

The European Union co-funded COMUNICAR (communication multimedia unit inside car) project designed and developed an integrated multimedia human–machine interface (HMI) able to manage a wide variety of driver information systems (from entertainment to safety). COMUNICAR proposed an innovative information provision paradigm, in which the on-vehicle HMI is able to tailor the delivery of the information in real time according to the actual driving context and the drivers workload. COMUNICAR adopted a user-centred design process involving an iterative development based on extensive user tests since the early phases of the project. This approach was particularly useful to define and improve the layout of the user interface and specify the rules that decide the scheduling and the modalities of the delivery of the information messages to the driver. This paper introduces the COMUNICAR concept and the user-centred flow of design. Then, a concrete case of user-test driven, iterative improvement of a systems functionality is presented. We also briefly describe two software tools that we have designed to enhance the development process in a user-centred perspective. Finally, the future evolution of the concept of smart and safe information scheduling is sketched and discussed.

---

Connecting the family with awareness systems

Awareness systems have attracted significant research interest for their potential to support interpersonal relationships. Investigations of awareness systems for the domestic environment have suggested that such systems can help individuals stay in touch with dear friends or family and provide affective benefits to their users. Our research provides empirical evidence to refine and substantiate such suggestions. We report our experience with designing and evaluating the ASTRA awareness system, for connecting households and mobile family members. We introduce the concept of connectedness and its measurement through the Affective Benefits and Costs of communication questionnaire (ABC-Q). We inform results that testify the benefits of sharing experiences at the moment they happen without interrupting potential receivers. Finally, we document the role that lightweight, picture-based communication can play in the range of communication media available.

---

A time-predictable VLIW processor and its compiler support

Time predictability is an important requirement for real-time embedded application domains such as automotive, air transportation, and multimedia processing. However, the architectural design of modern microprocessors mainly concentrates on improving the average-case performance, which can significantly compromise the time predictability and can make accurate worst-case performance analysis extremely difficult if not impossible. This paper studies the time predictability of VLIW (Very Long Instruction Word) processors and its compiler support. We analyze the impediments to time predictability for VLIW processors and propose compiler-based techniques to address these problems with minimal disturbance on the VLIW hardware design. The VLIW compiler is enhanced to support full if conversion, hyperblock scheduling, and intra-block nop insertion to enable efficient WCET (Worst Case Execution Time) analysis for VLIW processors. Our experiments indicate that the time-predictability of VLIW processor can be improved significantly.

Methods for quantitative usability requirements: a case study on the development of the user interface of a mobile phone

Quantitative usability requirements are a critical but challenging, and hence an often neglected aspect of a usability engineering process. A case study is described where quantitative usability requirements played a key role in the development of a new user interface of a mobile phone. Within the practical constraints of the project, existing methods for determining usability requirements and evaluating the extent to which these are met, could not be applied as such, therefore tailored methods had to be developed. These methods and their applications are discussed.

---

The 2007 IEEE CEC simulated car racing competition

This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process, we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.

---

Mapping functions and data redistribution for parallel files

Data distribution in memory or on disks is an important factor influencing the performance of parallel applications. On the other hand, programs or systems, like a parallel file system, frequently redistribute data between memory and disks. This paper presents a generalization of previous approaches of the redistribution problem. We introduce algorithms for mapping between two arbitrary distributions of a data set. The algorithms are optimized for multidimensional array partitions. We motivate our approach and present potential utilizations. The paper also presents a case study, the employment of mapping functions, and redistribution algorithms in a parallel file system.

Interacting with mobile services: an evaluation of camera-phones and visual tags

We present a study of using camera-phones and visual-tags to access mobile services. Firstly, a user-experience study is described in which participants were both observed learning to interact with a prototype mobile service and interviewed about their experiences. Secondly, a pointing-device task is presented in which quantitative data was gathered regarding the speed and accuracy with which participants aimed and clicked on visual-tags using camera-phones. We found that participants’ attitudes to visual-tag-based applications were broadly positive, although they had several important reservations about camera-phone technology more generally. Data from our pointing-device task demonstrated that novice users were able to aim and click on visual-tags quickly (well under 3 s per pointing-device trial on average) and accurately (almost all meeting our defined speed/accuracy tradeoff of 6% error-rate). Based on our findings, design lessons for camera-phone and visual-tag applications are presented.

---

The partitioned dynamic-priority scheduling of sporadic task systems

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal. A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.

Optimal virtual cluster-based multiprocessor scheduling

Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of us-edf{m/(2m−1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.

Prediction of dynamical,nonlinear, and unstable process behavior

Process scheduling techniques consider the current load situation to allocate computing resources. Those techniques make approximations such as the average of communication, processing, and memory access to improve the process scheduling, although processes may present different behaviors during their whole execution. They may start with high communication requirements and later just processing. By discovering how processes behave over time, we believe it is possible to improve the resource allocation. This has motivated this paper which adopts chaos theory concepts and nonlinear prediction techniques in order to model and predict process behavior. Results confirm the radial basis function technique which presents good predictions and also low processing demands show what is essential in a real distributed environment.

Wealth adjustment using a synergy between communication, cooperation, and one-fifth of wealth variables in an artificial society

Wealth distribution based on classic sugarscape model leads to a population increase and the Gini coefficient decrease when cooperation and communication parameters are taken into account. In another study, this model was developed by implying a receipt of one-fifth of the assets of the population and derived utilization for poor people. The results showed a relation between mortality decrease, population increase, and Gini coefficient decrease (equality increase). In a synergic process, the wealth adjustment based on sugarscape model underwent some experiments by implying communication and cooperation, and the mechanism of receiving and utilizing the assets. The results show that the population increase and the Gini coefficient decrease play an important role in wealth adjustment.

---

Language resources for Hebrew

We describe a suite of standards, resources and tools for computational encoding and processing of Modern Hebrew texts. These include an array of XML schemas for representing linguistic resources; a variety of text corpora, raw, automatically processed and manually annotated; lexical databases, including a broad-coverage monolingual lexicon, a bilingual dictionary and a WordNet; and morphological processors which can analyze, generate and disambiguate Hebrew word forms. The resources are developed under centralized supervision, so that they are compatible with each other. They are freely available and many of them have already been used for several applications, both academic and industrial.

Lose Fat, Not Muscle: An Examination of Supervisor Reduction in Discrete-Event Systems

This paper is concerned with the elimination of unnecessary states in discrete-event system control agents. Several approaches to supervisor reduction are studied and a new relation between agents, comparability, is defined to encapsulate most of the concepts found in the aforementioned methods. This relation is also proven to be preserved under conjunction, which is commonly employed to determine the centralized representation of two decentralized DES supervisors.

Multimodal support to group dynamics

The complexity of group dynamics occurring in small group interactions often hinders the performance of teams. The availability of rich multimodal information about what is going on during the meeting makes it possible to explore the possibility of providing support to dysfunctional teams from facilitation to training sessions addressing both the individuals and the group as a whole. A necessary step in this direction is that of capturing and understanding group dynamics. In this paper, we discuss a particular scenario, in which meeting participants receive multimedia feedback on their relational behaviour, as a first step towards increasing self-awareness. We describe the background and the motivation for a coding scheme for annotating meeting recordings partially inspired by the Bales’ Interaction Process Analysis. This coding scheme was aimed at identifying suitable observable behavioural sequences. The study is complemented with an experimental investigation on the acceptability of such a service.

---

ONTRACK: Dynamically adapting music playback to support navigation

Listening to music on personal, digital devices whilst mobile is an enjoyable, everyday activity. We explore a scheme for exploiting this practice to immerse listeners in navigation cues. Our prototype, ONTRACK, continuously adapts audio, modifying the spatial balance and volume to lead listeners to their target destination. First we report on an initial lab-based evaluation that demonstrated the approach’s efficacy: users were able to complete tasks within a reasonable time and their subjective feedback was positive. Encouraged by these results we constructed a handheld prototype. Here, we discuss this implementation and the results of field-trials. These indicate that even with a low-fidelity realisation of the concept, users can quite effectively navigate complicated routes.

---

An approach to enterprise process dynamic modeling supporting enterprise process evolution

This study presents an evolutionary approach to support dynamic enterprise modeling for enterprise process cooperative scheduling and management. In this paper, an evolutionary dynamic enterprise process modeling method was proposed from the concepts of enterprise process evolution to zero-time enterprise modeling and layered complex enterprise modeling. Based on an autonomous agent development platform, an agent-based enterprise collaborative modeling environment has been implemented by integrating several software resource agents that wrap main function modules of EPMS. Scheduling strategies, algorithms, and process-driven cooperative scheduling mechanism are also discussed.

Evolving strategy for a probabilistic game of imperfect information using genetic programming

We provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. Ant Wars contestants are virtual ants collecting food on a grid board in the presence of a competing ant. BrilliAnt has been evolved through a competitive one-population coevolution using genetic programming and fitnessless selection. In this paper, we detail the evolutionary setup that lead to BrilliAnt’s emergence, assess its direct and indirect human-competitiveness, and describe the behavioral patterns observed in its strategy.

---