This book constitutes the refereed proceedings of the Third International Frontiers of Algorithmics Workshop, FAW 2009, held in Hefei, Anhui, China, in June 2009. The 33 revised full papers presented together with the...
详细信息
ISBN:
(数字)9783642022708
ISBN:
(纸本)9783642022692
This book constitutes the refereed proceedings of the Third International Frontiers of Algorithmics Workshop, FAW 2009, held in Hefei, Anhui, China, in June 2009. The 33 revised full papers presented together with the abstracts of 3 invited talks were carefully reviewed and selected from 87 submissions. The papers are organized in topical sections on graph algorithms; game theory with applications; graph theory, computational geometry; machine learning; parameterized algorithms, heuristics and analysis; approximation algorithms; as well as pattern recognition algorithms, large scale data mining.
Applications performance is a criterion for system evaluation, and hence performance tuning for these applications is of great interest. One such benchmark application is highperformance Linpack (HPL). Although guide...
详细信息
In this paper, we describe our goal of an effective course management system for assisting course managers to make informed decisions about what materials should be most appropriate to be presented to students (learne...
详细信息
ISBN:
(纸本)9789834251253
In this paper, we describe our goal of an effective course management system for assisting course managers to make informed decisions about what materials should be most appropriate to be presented to students (learners) and what learning strategies or methods should be used for the students. The system is supported by our design of a novel framework for user-driven data analytics in the cloud. Different modules of the framework will be illustrated in detail in the context of course management.
Sequence alignment is an important problem in computational biology and finding the longest common subsequence (LCS) of multiple biological sequences is an essential and effective technique in sequence alignment. A ma...
详细信息
ISBN:
(纸本)9789881701299
Sequence alignment is an important problem in computational biology and finding the longest common subsequence (LCS) of multiple biological sequences is an essential and effective technique in sequence alignment. A major computational approach for solving the LCS problem is dynamic programming. Several dynamic programming methods have been proposed to have reduced time and space complexity. As databases of biological sequences become larger, parallel algorithms become increasingly important to tackle large size problems. In the meantime, general-purpose computing on graphics processing units (GPGPU) has emerged as a promising technology for cost-effective highperformancecomputing. In this paper, we develop an efficient parallel algorithm on GPUs for the LCS problem. We propose a new technique that changes the data dependency in the score table used by dynamic programming algorithms to enable higher degrees of parallelism. The algorithm takes advantage of the large number of processing units and the unique memory-accessing properties of GPUs to achieve highperformance. The algorithm was implemented on Nvidia 9800GT GPUs and tested on randomly generated sequences of different lengths. The experiment results show that the new algorithm is about 6 times faster on GPUs than on typical CPUs and is 3 times faster than an existing efficient parallel algorithm, the diagonal parallel algorithm.
This is one of our series works on discrete energy analysis of the variable-step BDF *** this part,we present stability and convergence analysis of the third-order BDF(BDF3)schemes with variable steps for linear diffu...
详细信息
This is one of our series works on discrete energy analysis of the variable-step BDF *** this part,we present stability and convergence analysis of the third-order BDF(BDF3)schemes with variable steps for linear diffusion equations,see,e.g.,[SIAM ***.,58:2294-2314]and[***.,90:1207-1226]for our previous works on the BDF2 *** this aim,we first build up a discrete gradient structure of the variable-step BDF3 formula under the condition that the adjacent step ratios are less than 1.4877,by which we can establish a discrete energy dissipation ***-robust stability and convergence analysis in the L^(2) norm are then *** the mesh robustness means that the solution errors are well controlled by the maximum time-step size but independent of the adjacent time-step *** also present numerical tests to support our theoretical results.
Three protocols for gossip-based failure detection services in large-scale heterogeneous clusters are analyzed and compared. The basic gossip protocol provides a means by which failures can be detected in large distri...
Three protocols for gossip-based failure detection services in large-scale heterogeneous clusters are analyzed and compared. The basic gossip protocol provides a means by which failures can be detected in large distributed systems in an asynchronous manner without the limits associated with reliable multicasting for group communications. The hierarchical protocol leverages the underlying network topology to achieve faster failure detection. In addition to studying the effectiveness and efficiency of these two agreement protocols, we propose a third protocol that extends the hierarchical approach by piggybacking gossip information on application-generated messages. The protocols are simulated and evaluated with a fault-injection model for scalable distributed systems comprised of clusters of workstations connected by high-performance networks, such as the CPlant system at Sandia National Laboratories. The model supports permanent and transient node and link failures, with rates specified at simulation time, for processors functioning in a fail-silent fashion. Through high-fidelity, CAD-based modeling and simulation, we demonstrate the strengths and weaknesses of each approach in terms of agreement time, number of gossips, and overall scalability.
Gossip protocols and services provide a means by which failures can be detected in large, distributed systems in an asynchronous manner without the limits associated with reliable multicasting for group communications...
Gossip protocols and services provide a means by which failures can be detected in large, distributed systems in an asynchronous manner without the limits associated with reliable multicasting for group communications. Extending the gossip protocol such that a system reaches consensus on detected faults can be performed via a flat structure, or it can be hierarchically distributed across cooperating layers of nodes. In this paper, the performance of gossip services employing flat and hierarchical schemes is analyzed on an experimental testbed in terms of consensus time, resource utilization and scalability. performance associated with a hierarchically arranged gossip scheme is analyzed with varying group sizes and is shown to scale well. Resource utilization of the gossip-style failure detection and consensus service is measured in terms of network bandwidth utilization and CPU utilization. Analytical models are developed for resource utilization and performance projections are made for large system sizes.
Functional dependencies (FDs) form a valuable ingredient for various data management tasks. However, existing methods can hardly discover practical and interpretable FDs, especially in large noisy real-life datasets. ...
详细信息
Recently, resource virtualisation has been proven effective for deploying large-scale IT-infrastructures, such as grids and clouds. However, many studies also indicate that the system's energy-efficiency will be r...
详细信息
Gossip protocols provide a means by which failures can be detected in large, distributed systems in an asynchronous manner without the limits associated with reliable multicasting for group communications. However, in...
Gossip protocols provide a means by which failures can be detected in large, distributed systems in an asynchronous manner without the limits associated with reliable multicasting for group communications. However, in order to be effective with application recovery and reconfiguration, these protocols require mechanisms by which failures can be detected with system-wide consensus in a scalable fashion. This paper presents three new gossip-style protocols supported by a novel algorithm to achieve consensus in scalable, heterogeneous clusters. The round-robin protocol improves on basic randomized gossiping by distributing gossip messages in a deterministic order that optimizes bandwidth consumption. Redundant gossiping is completely eliminated in the binary round-robin protocol, and the round-robin with sequence check protocol is a useful extension that yields efficient detection times without the need for system-specific optimization. The distributed consensus algorithm works with these gossip protocols to achieve agreement among the operable nodes in the cluster on the state of the system featuring either a flat or a layered design. The various protocols are simulated and evaluated in terms of consensus time and scalability using a high-fidelity, fault-injection model for distributed systems comprised of clusters of workstations connected by high-performance networks.
暂无评论