7267319
Symbolic expression analysis for compiled communication
Enabling circuit switching in multiprocessor systems has the potential to achieve more efficient communication with lower cost compared to packet/wormhole switching. However, in order to accomplish this efficiently, assistance from the compiler is required to reveal the communication pattern in the parallel application. In this paper we present symbolic expression analysis techniques in a MPI parallel compiler. Symbolic expression analysis allows the identification and representation of the communication pattern and also assists in the determination of communication phases in MPI parallel applications at compile-time. We demonstrate that using the compiler analysis based on symbolic expression analysis to determine the communication pattern and phases provides an average of 2.6 times improvement in message delay over a threshold-based runtime system for our benchmarks with a maximum improvement of 9.7 times.
44740953
Non-Uniform "Fat-Meshes" for Chip Multiprocessors
This paper studies the traffic hot spots of mesh networks in the context of chip multiprocessors. To mitigate these effects, this paper describes a non-uniform fat-mesh extension to mesh networks, which are popular for chip multiprocessors. The fat-mesh is inspired by the fat-tree and dedicates additional links for connections with heavy traffic (e.g. near the center) with fewer links for lighter traffic (e.g. near the periphery). Two fat-mesh schemes are studied based on the traffic requirements of chip multiprocessors using dimensional ordered XY routing and a randomized XY-YX routing algorithms, respectively. Analytical fat-mesh models are constructed by theoretically presenting the expressions for the traffic requirements of personalized all-to-all traffic for both the raw message numbers and their normalized equivalents. We demonstrate how traffic scales for a traditional mesh compared to a non-uniform fat mesh. Simulation results demonstrate that using same number of physical links the non-uniform fat-mesh can achieve better performance than a uniform fat-mesh mesh using both synthetic traffic patterns and splash-2 benchmark traces.
12630564
Develop a Computational Trust Prototype for the Semantic Web
Nowadays, more and more research has focused on the trust management of the Semantic Web. Some mature technologies from many fields such as multiagent systems, social network analysis and artificial intelligence have been introduced to this field. However, some unique characteristics of the Semantic Web are more or less ignored. In this paper, we try to explore the semantic aspects of the trust management. We present DartTrust, a trust prototype for the semantic web in the application context of Traditional Chinese Medicine (TCM). We introduce RCSW - a Reputation-Chain trust model for the Semantic Web, which incorporates pairwise trust factor and reliable factor and constructs an edge-weighted graph to calculate trust ratings. We define a small trust ontology to illustrate the trust relationships. The trust ontology is described in OWL that can be understood and processed by machines. Therefore, DartTrust can provide reasoning functions and facilitate trust management with little human effort. As a demonstration of the prototype, we present its implementation on Traditional Chinese Medicine (TCM) at the end of this paper.
21795877
An Eulerian Path Approach to Global Multiple Alignment for DNA Sequences
With the rapid increase in the dataset of genome sequences, the multiple sequence alignment problem is increasingly important and frequently involves the alignment of a large number of sequences. Many heuristic algorithms have been proposed to improve the speed of computation and the quality of alignment. We introduce a novel approach that is fundamentally different from all currently available methods. Our motivation comes from the Eulerian method for fragment assembly in DNA sequencing that transforms all DNA fragments into a de Bruijn graph and then reduces sequence assembly to a Eulerian path problem. The paper focuses on global multiple alignment of DNA sequences, where entire sequences are aligned into one configuration. Our main result is an algorithm with almost linear computational speed with respect to the total size (number of letters) of sequences to be aligned. Five hundred simulated sequences (averaging 500 bases per sequence and as low as 70% pairwise identity) have been aligned within three minutes on a personal computer, and the quality of alignment is satisfactory. As a result, accurate and simultaneous alignment of thousands of long sequences within a reasonable amount of time becomes possible. Data from an Arabidopsis sequencing project is used to demonstrate the performance.
16272826
Analyzing the impact of on-chip network traffic on program phases for CMPs
It is known that the execution of programs exhibits repetitive phases; in other words, the execution of programs can be partitioned into segments of execution, during which the application exhibits unique architectural properties. This property has been used for various optimization goals. In addition, phase information is utilized to reduce the run time of the architectural simulation. Conventionally, an application is examined in an architecture-independent manner (such as the number of times a basic block is executed) to extract information about the phases and then only the representative execution intervals are executed to analyze architectural choices. We claim that such approaches are becoming inadequate in the many-core era as application execution is not dominated by the instructions only, but instead the communication structure of the application is becoming as important as the instruction behavior. Hence, we propose to utilize communication behavior to determine the phases of an application. Our results reveal that the inclusion of the communication information can increase the accuracy of the phase detection significantly. Specifically, for SPLASH2 and MineBench applications, the average (geometric mean) CPI error rate with the instruction-based phase detection is 11.01%, while our phase detection scheme has an average error rate of 3.41% when compared to the simulations that run the applications to completion.
12319923
Decoding Digital Information from the Cascaded Heterogeneous Chaotic Systems
In this paper, we propose a new approach to breaking down chaotic communication scheme by attacking its encryption keys. A remarkable advancement is that it can decode the hidden message exactly. This makes it become possible to break down some cascaded chaotic communication systems. We also decode digital information from the cascaded heterogeneous chaotic communication system and give the simulation results.
8166991
On Destination Set in IP-Level Topology Measurement
We present a thorough investigation of four issues with the destination set in IP-level topology measurement. (1) To evaluate the completeness of the destination set, we measured by brute force and found that a half of edges will be missed by the uniform random selection (URS) method which was adopted by well-known CAIDA' skitter. (2) Two potential reasons for edge missing, the short-term routing dynamics and the subnetting technique, were investigated with the last-hop selection method and the bisection selection method respectively. And the results showed that the subnetting technique is the main reason. (3) To select destinations efficiently, we presented the minimum cover selection (MCS) method which performed better than the URS method on 75% of networks over three months. (4) Finally, to investigate the bias of topology characterization, we measured a destination set larger than before and discovered a Chinese topology whose size is 5 times as large as that discovered by skitter. The comparison between characteristics of skitter's topology and ours indicated that the small destination set trends to miss the information on marginal networks.