14206506
The role of diverse populations in phylogenetic analysis
The most popular approaches for reconstructing phylogenetic trees attempt to solve NP-hard optimization criteria such as maximum parsimony (MP). Currently, the best-performing heuristic for reconstructing MP trees is Recursive-Iterative DCM3 (Rec-I-DCM3), which uses a single tree (or solution) to guide its way through an exponentially-sized tree space. To improve performance further, we designed Cooperative Rec-I-DCM3, a population-based approach for utilizing a population of Rec-I-DCM3 trees.We compare the performance of Cooperative Rec-I-DCM3 to Rec-I-DCM3 on four large biological datasets. Of particular interest is Cooperative Rec-I-DCM3's selection criteria for maintaining a population of solutions. Our experiments reveal that diverse populations outperform Rec-I-DCM3 in terms of average rates of convergence to best-known MP scores. To achieve greater performance, we designed an elitist population strategy, in which each solution's tree score matches that of the best score found in each generation. The elitist strategy was by far the worst overall performer in our experiments. Hence, being greedy is not always the best approach. Instead, a population of diverse solutions allows our cooperative algorithm to achieve the greatest performance improvements.
6340669
Phylospaces: reconstructing evolutionary trees in tuple space
Phylospaces is a novel framework for reconstructing evolutionary trees in tuple space, a distributed shared memory that permits processes to communicate and coordinate with each other. Our choice of tuple space as a concurrency model is somewhat unusual, given the prominence and success of pure message passing models, such as MPI. We use phylospaces to devise cooperative Rec-I-DCM3, a population-based strategy for navigating tree space. Cooperative Rec-I-DCM3 is based on Rec-I-DCM3, the fastest sequential algorithm under maximum parsimony. We compare the performance of the algorithms on two datasets consisting of 2,000 and 7,769 taxa, respectively. Our results demonstrate that cooperative Rec-I-DCM3 outperforms its sequential counterpart by at least an order of magnitude
28781124
From Sequential Processes to Grid Computation
We introduce an extended model for view-centric reasoning, EVCR, that provides more comprehensive and flexible abstractions for representing actual concurrency. The theory of Communicating Sequential Processes (CSP) provides an interleaved semantics for reasoning about concurrency through a sequentialized trace of events recorded by an idealized observer. The theory of View-Centric Reasoning (VCR) extended CSP with notions of parallel events and views, and lazy observation, to represent the true concurrency of simultaneous events and multiple, possibly imperfect observers. But VCR could be more general still, since its events, like those of CSP, are instantaneous. This restriction precludes the possibility of observing events that partially overlap in time. EVCR permits partially overlapping events to be observed and recorded by a lazy observer. The result is a more general model of concurrency; one that is more appropriate for reasoning about network functioning and, in particular, grid computation.
6308382
Cooperative Rec-I-DCM3: A Population-Based Approach for Reconstructing Phylogenies
In this paper, we study the use of cooperation as a technique for designing faster algorithms for reconstructing phylogenetic trees. Our focus is on the use of cooperation to reconstruct trees based on maximum parsimony. Our baseline algorithm is Rec-I-DCM3, the best-performing MP algorithm known-to-date. Our results demonstrate that cooperation does improve the performance of the baseline algorithm by at least an order of magnitude in terms of running time. The use of cooperation also established a new best known score on one of our datasets.
5639011
A Characterization of Lazy and Eager Semantic Solutions to the Linda Predicates Ambiguity Problem
The problems associated with Linda predicate operations inp() and rdp() are well known but not always well understood. One problem, from a purely academic standpoint, is that of semantic ambiguity in the case of failure. Despite this problem, commercial tuple space implementations all provide some version of the Linda predicate operations, and thus, problems concerning safety and liveness arise. Solutions to address these problems range from proposing extensions to an existing model of computation (CSP) to proposing alternative definitions for the Linda predicate operations themselves. While these solutions may at first appear unrelated, it is possible to relate these two disparate approaches in the context of lazy and eager semantics. The benefits of this characterization include a clearer understanding of the Linda predicates ambiguity problem, two respective solutions to this problem, and the importance of considering both lazy and eager semantic perspectives as techniques for problem solving in parallel and distributed systems.
7755497
Teaching Java Concurrency to CS vs IT Students: A Matter of Emphasis
A number of colleges and universities have recently added new degree programs in Information Technology (IT), or added IT components to existing Computer Science (CS) programs. Java language and technology are almost inescapable elements of both CS and IT programs. One of Java's more advanced features, languagelevel support for concurrency in the form of explicit multithreading, is important to both CS and IT students, but for different reasons. Teaching Java concurrency to CS and IT students, therefore, presents different challenges and requires emphasizing the topic in different ways. We discuss these issues, and present our experiences from CS and IT classes taught recently, in which Java concurrency was a topic.
52872904
Simulative analysis of dynamic scheduling heuristics for reconfigurable computing of parallel applications
The demand for processing power has been ever increasing with the growth of high-performance computing (HPC) applications and so have the constraints restricting the solutions to such requirements. High-performance distributed and parallel computing and custom-built, hardware-based computing have attempted to address this problem with some success but at a substantial cost. Recently, systems augmented with Field-Programmable Gate Arrays (FPGAs) offering a fusion of traditional parallel and distributed machines with customizable and dynamically reconfigurable hardware have emerged as a cost-effective alternative to traditional systems. However, providing a robust runtime environment for such systems to which HPC users have become accustomed has been fraught with numerous challenges. Dynamic scheduling of large-scale HPC applications in such parallel reconfigurable computing (RC) environments is one such challenge and has not been sufficiently studied to our knowledge. In this paper, we simulatively analyze the performance of several common HPC scheduling heuristics that can be used by an automated job management service to schedule application tasks on a parallel RC system. We also present a performance prediction model which the scheduling heuristics employ to schedule several common HPC applications on a collection of typical FPGA processing platforms.
7182268
Accelerating scientific applications with the SRC-6 reconfigurable computer: methodologies and analysis
Reconfigurable computing offers the promise of performing computations in hardware to increase performance and efficiency while retaining much of the flexibility of a software solution. Recently, the capacities of reconfigurable computing devices, like field programmable gate arrays, have risen to levels that make it possible to execute 64b floating-point operations. SRC Computers has designed the SRC-6 MAPstation to blend the benefits of commodity processors with the benefits of reconfigurable computing. In this paper, we describe our effort to accelerate the performance of several scientific applications on the SRC-6. We describe our methodology, analysis, and results. Our early evaluation demonstrates that the SRC-6 provides a unique software stack that is applicable to many scientific solutions and our experiments reveal the performance benefits of the system.
5888435
Visualization components for persistent conversations
An appropriately designed interface to persistent, threaded conversations could reinforce socially beneficial behavior by prominently featuring how frequently and to what degree each user exhibits such behaviors. Based on the data generated by the Netscan data-mining project [9], we have developed a set of tools for illustrating the structure of discussion threads like those found in Usenet newsgroups and the patterns of participation within the discussions. We describe the benefits and challenges of integrating these tools into a multi-faceted dashboard for navigating and reading discussions in social cyberspaces like Usenet and related interaction media. Visualizations of the structure of online discussions have applications for research into the sociology of online groups as well as possible interface designs for their members.
402019
Conversation trees and threaded chats
Chat programs and instant messaging services are increasingly popular among Internet users. However, basic issues with the interfaces and data structures of most forms of chat limit their utility for use in formal interactions (like group meetings) and decision-making tasks. In this paper, we discuss Threaded Text Chat, a program designed to address some of the deficiencies of current chat programs. Standard forms of chat introduce ambiguity into interaction in a number of ways, most profoundly by rupturing connections between turns and replies. Threaded Chat presents a solution to this problem by supporting the basic turn-taking structure of human conversation. While the solution introduces interface design challenges of its own, usability studies show that users' patterns of interaction in Threaded Chat are equally effective, but different (and possibly more efficient) than standard chat programs.
45488813
Parallel application performance on shared high performance reconfigurable computing resources
The use of a network of shared, heterogeneous workstations each harboring a reconfigurable computing (RC) system offers high performance users an inexpensive platform for a wide range of computationally demanding problems. However, effectively using the full potential of these systems can be challenging without the knowledge of the system's performance characteristics. While some performance models exist for shared, heterogeneous workstations, none thus far account for the addition of RC systems. Our analytic performance model includes the effects of the reconfigurable device, application load imbalance, background user load, basic message passing communication, and processor heterogeneity. The methodology proves to be accurate in characterizing these effects for applications running on shared, homogeneous, and heterogeneous HPRC resources. The model error in all cases was found to be less than 5% for application runtimes greater than 30s, and less than 15% for runtimes less than 30s.