31267474
Skewed Data Partition and Alignment Techniques for Compiling Programs on Distributed Memory Multicomputers
Minimizing data communication over processors is the key to compile programs for distributed memory multicomputers. In this paper, we propose new data partition and alignment techniques for partitioning and aligning data arrays with a program in a way of minimizing communication over processors. We use skewed alignment instead of the dimension-ordered alignment techniques to align data arrays. By developing the skewed scheme, we can solve more complex programs with minimized data communication than that of the dimension-ordered scheme. Finally, the experimental results show that our proposed scheme has more opportunities to align data arrays such that data communications over processors can be minimized.
17694458
Optimal broadcasting on incomplete star graph interconnection networks
Broadcasting is an important collective communication operation in many applications which use parallel computing. In this paper, we focus on designing broadcasting algorithms for general incomplete star graphs. We propose two optimal one-to-all broadcasting algorithms for incomplete star graphs with a single-port communication model. An incomplete star graph with N nodes, where (n - 1)! < N < n!, is a subgraph of an n-dimensional star graph. The first scheme is single-message one-to-all broadcasting that takes O(nlogn) steps. The second one is multi-message one-to-all broadcasting that takes O(nlogn + m) steps.
6997568
Gathering-Load-Balanced Tree Protocol for Wireless Sensor Networks
Wireless communications and digital electronics have enabled the development of low-power, low-cost, multifunctional sensors. The functionality of sensor network mainly is the measurement collection. The previous proposed protocols mainly focus on broadcasting tree structure, but it may not be efficient in data gathering. In this paper, we propose novel tree architecture that is a dynamic, adjustable, load-balanced tree in sensor networks to decrease the energy utilization and to prolong the lifetime of sensors. A load-balanced tree can share the forwarding loads between non-leaf nodes. Due to the limit of tree topology, we try to adjust forming a tree that has similar amount of children between non-leaf nodes. When the energy of non-leaf node is lower than a designated threshold, the tree structure can be readjusted to prolong the lifetime of tree. In simulation, we compare our protocol with different adjustment phases and an existed protocol. From the result, our protocol can have better performance than others
8131087
Multipath-Based Multicasting Strategies for Wormhole-Routed Star Graph Interconnection Networks
The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we present a multipath-based multicast routing model for wormholerouted star graph networks, propose two efficient multipath routing schemes, and contrast the performance of the proposed schemes with the performance of the scheme presented in our previous work. Both of the two proposed schemes have been proven to be deadlock-free. The first scheme, simplemultipath routing, uses multiple independent paths for concurrent multicasting. The second scheme, two-phase multipath routing, includes two phases: source-to-relay and relay-to-destination. For each phase, multicasting is carried out using simple multipath routing. Experimental results show that, for short and medium messages with small message startup latencies, the proposed schemes reduce multicast latency more efficiently than other schemes.
45055182
Mining frequent tree-like patterns in large datasets
Sequential pattern mining is crucial to data mining domains. This paper proposes a novel data mining approach for exploring hierarchical tree structures, named tree-like patterns, representing the relationships for a pair of items in a sequence. Using tree-like patterns, the relationships for a pair of items can be identified in terms of the cause and effect. A novel technique that efficiently counts support values for tree-like patterns using a queue structure is proposed. In addition, this paper addresses an efficient scheme for determining the frequency of a tree-like pattern in a sequence using a dynamic programming approach. Each tree-like pattern embedded in a sequence is considered to have a certain valuable meaning or the degree of importance used in different applications. Two addressed formulas are applied to determine the degree of significance for a specific sequence, which denotes the degree of consecutive items in a tree-like pattern for a sequence. The larger the degree of significance a tree-like pattern has, the more the tree-like pattern is compacted in the sequence. The characteristics differentiating the explored patterns from those obtained with other schemes are discussed. A simulation analysis of the proposed data mining approach is utilized to demonstrate its efficacy. Finally, the proposed approach is designed and implemented in a data mining system integrated into a novel e-learning platform.
12245644
Multicast communication in wormhole-routed star graph interconnection networks
Multicast, an important communication mechanism, is frequently applied in parallel computing. The star graph interconnection network, when compared with the hypercube network, being with low degree and small diameter, has been recognized to be an attractive alternative to the popular hypercube network. In this paper, we derive a node labeling formula based on a hamiltonian path and propose four efficient multicast routing schemes in wormhole-routed star networks with multidestination routing capability. All of the four proposed schemes are path-based and deadlock-free. The first scheme, dual-path routing, sends the message in parallel through two independent paths (toward high label nodes and low label nodes). The second one, shortcut-node-based dual-path routing, is similar to dual-path routing except that the routing tries to find a shortcut node to route the message as soon as possible to reduce the length of transmission path. The third one, multipath routing, is a multiple dual-path routing strategy that includes source-to-relay and relay-to-destination phases. The last scheme, proximity grouping routing, is similar to multipath routing except that in the partitioning step of source and destination nodes the relation of spatial locality of nodes is also taken into account to reduce the length of transmission paths. Finally, the experimental results are given to show that the performance based on unicast-based and traditional hamiltonian-path routing schemes can be improved significantly by the four proposed routing schemes respectively.
44631758
Agent-based forwarding strategies for reducing location management cost in mobile networks
A major issue with location management in mobile wireless networks is the high cost associated with location updates and searches. A search occurs when a caller needs to connect to a mobile user whose location is unknown to the caller and the network must locate the callee. An update occurs when a mobile user moves into a new registration area and the network is informed of the location change. We propose and analyze a class of new agent-based forwarding strategies with the objective to reduce the location management cost in mobile wireless networks. We develop analytical Markov models to compare the performance of the proposed strategies with existing location management schemes to demonstrate their feasibility and also to reveal conditions under which the proposed schemes are superior to existing ones.
26835658
On the test allocations for the best lower bound performance of partition testing
A partition testing strategy divides the program's input domain into subdomains according to a partitioning scheme, and selects test cases from each subdomain according to a test allocation scheme. Previous studies have shown that partition testing strategies can be very effective or very ineffective in detecting faults, depending on both the partitioning scheme and the test allocation scheme. Given a partitioning scheme, the maximin criterion chooses a test allocation scheme that will maximally improve the lower bound performance of the partition testing strategy. In an earlier work, we have proved that the Basic Maximin Algorithm can generate such a test allocation scheme. In this paper, we derive further properties of the Basic Maximin Algorithm and present the Complete Maximin Algorithm that generates all possible test allocation schemes that satisfy the maximin criterion.
17432425
Structure analysis for dynamic software architecture
The open and dynamic Internet environment greatly urges software entities that are distributed on different locations to coordinate with each other to accomplish a computing task. Software architecture is applied to abstract the software entities to be components and the coordination between them to be connectors and then a model is extracted as the architecture on which the design, analysis and verification are based. Currently, the notion of dynamic software architectures that can modify their architecture and enact modifications during the system execution has become one of the most active research areas. In this paper, we focus on the dynamic evolution of system structure other than coordination mechanisms (e.g. communication protocols). It is widely recognized that some restrictions should be imposed on the system evolution to ensure that the system structure may remain one style or transform within a scope. These conditions, to a large extent, make the system execute under control as expected.
33188963
Improving the quality of classification trees via restructuring
The classification-hierarchy table developed by Chen and Poon (1996) provides a systematic approach to construct classification trees from given sets of classifications and their associated classes. The paper enhances their study by defining a metric to measure the "quality" of a classification tree, and providing an algorithm to improve this quality.
16174340
A new encryption algorithm for image cryptosystems
Abstract There are two major differences of the characteristics of the text data and image data. One difference is that the size of image data is usually much larger than that of text data. The other is that plain data rarely permit loss when a compression technique is used, but image data do. In this paper, we design an efficient cryptosystem for images. Our method is based on vector quantization, which is one of the popular image compression techniques. Our method can achieve the following two goals. One goal is to design a high security image cryptosystem. The other goal is to reduce computational complexity of the encryption and decryption algorithms.