In parallelizing compilers on distributed memory systems, distributions of irregular sized array blocks are provided for load balancing and irregular problems. The irregular data redistribution is different from the regular block-cyclic redistribution. This paper is devoted to scheduling message for irregular data redistribution that attempt to obtain suboptimal solutions while satisfying the minimal communication costs condition and the minimal step condition. Based on the list scheduling, an efficient algorithm is developed and its experimental results are compared with previous algorithms. The improved list algorithm provides more chance for conflict messages in its relocation phase, since it allocates conflict messages through methods used in a divide-and-conquer algorithm and a relocation algorithm proposed previously. The method of selecting the smallest relocation cost guarantees that the improved list algorithm is more efficient than the other two in average.

Due to the distributed nature, mobile ad-hoc networks (MANETs) are vulnerable to various attacks, resulting in distrusted communications. To achieve trusted communications, it is important to build trusted routes in routing algorithms in a self-organizing and decentralized fashion. This paper proposes a trusted routing to locate and to preserve trusted routes in MANETs. Instead of using a hard security mechanism, we employ a new dynamic trust mechanism based on multiple constraints and collaborative filtering. The dynamic trust mechanism can effectively evaluate the trust and obtain the precise trust value among nodes, and can also be integrated into existing routing protocols for MANETs, such as ad hoc on-demand distance vector routing (AODV) and dynamic source routing (DSR). As an example, we present a trusted routing protocol, based on dynamic trust mechanism, by extending DSR, in which a node makes a routing decision based on the trust values on its neighboring nodes, and finally, establish a trusted route through the trust values of the nodes along the route in MANETs. The effectiveness of our approach is validated through extensive simulations.

A fundamental problem in a pure Peer-to-Peer (P2P) file sharing system is how to protect the anonymity of peer nodes when providing efficient data access services. Most of existing work mainly focus on how to provide the initiator anonymity, but neglect the anonymity of the responder. In this paper, we propose a multicast-based protocol, called Mapper, for efficient file sharing with mutual anonymity. By seamlessly combining the technologies of multi-proxy and IP multicast together, the proposed protocol guarantees mutual anonymity during the entire session of file retrieval. Furthermore, Mapper replicates requested files inside the multicast group, so file distribution can be adjusted adaptively and the cost for multicast can be further reduced. Results of both simulations and theoretical analyses demonstrate that Mapper possesses the merits of scalability, reliability, and high adaptability.

Array redistribution is required very often in programs on distributed memory parallel computers. It is essential to use efficient algorithms for redistribution, otherwise the performance of programs may degrade considerably. In this paper, we focus on automatic generation of communication routines for multi-dimensional redistribution. The principal advantage of this work is to gain the ability to handle redistribution between arbitrary source and destination processor sets and between arbitrary source and destination distribution schemes. We have implemented these algorithms using Parallelware communication library. Some experimental results show the efficiency and flexibility of our techniques compared to the other redistribution works.

In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

Many parallel applications involve different independent tasks with their own data. Using the MPMD model, programmers can have a modular view and simplified structure of the parallel programs. Although MPI supports both SPMD and MPMD models for programming, MPI libraries do not provide an efficient way for task communication for the MPMD model. We have developed a programming environment, called ClusterGOP, for building and developing parallel applications. Based on the graph-oriented programming (GOP) model, ClusterGOP provides higher-level abstractions for message-passing parallel programming with the support of software tools for developing and running parallel applications. In this paper, we describe how ClusterGOP supports programming of MPMD parallel applications on top of MPI. We discuss the issues of implementing the MPMD model in ClusterGOP using MPI and evaluate the performance by using example applications.

This paper shows how to use sticker to construct solution space of DNA for the library sequences in the set-packing problem and the clique problem. Then, with biological operations, we propose DNA-based algorithms to remove illegal solutions and to find legal solutions for the set-packing and clique problems from the solution space of sticker. Any NP-complete problem in Cook's Theorem can be reduced and solved by the proposed DNA-based computing approach if its size is equal to or less than that of the set-packing problem. Otherwise, Cook's Theorem is incorrect on DNA-based computing and a new DNA algorithm should be developed from the characteristics of the NP-complete problem. Finally, the result to DNA simulation is given.

In this paper, Message Passing Interface (MPI) techniques are used to implement high-order full 3-D Navier-Stokes equations in multi-domain applications. A two-domain interface with five-point overlapping used previously is expanded to a multi-domain computation. There are normally two approaches for this expansion. One is to break up the domain into two parts through domain decomposition (say, one overlapping), then using MPI directives to further break up each domain into n parts. Another is to break the domain up into 2n parts with (2n-1) overlappings. In our present effort, the latter approach is used and finite-size overlappings are employed to exchange data between adjacent multi-dimensional sub-domains. It is an alternative way to parallelize the high-order full 3-D Navier-Stokes equations into multi-domain applications without adding much complexity. Results with high-order boundary treatments show consistency among multi-domain calculations and single-domain results.

We propose a Multiple Zones-based (M-Zone) routing protocol to discover node-disjoint multiplath routing efficiently and effectively in large-scale MANETs. Compared with single path routing, multipath routing can improve robustness, load balancing and throughput of a network. However, it is very difficult to achieve node-disjoint multipath routing in large-scale MANETs. To ensure finding node-disjoint multiple paths, the M-Zone protocol divides the region between a source and a destination into multiple zones based on geographical location and each path is mapped to a distinct zone. Performance analysis shows that M-Zone has good stability, and the control complexity and storage complexity of M-Zone are lower than those of the well-known AODVM protocol. Simulation studies show that the average end-to-end delay of M-Zone is lower than that of AODVM and the routing overhead of M-Zone is less than that of AODVM.

Many applications of wireless sensor networks (WSNs) require secure group communications. The WSNs are normally operated in unattended, harsh, or hostile environment. The adversaries may easily compromise some sensor nodes and abuse their shared keys to inject false sensing reports or modify the reports sent by other nodes. Once a malicious node is detected, the group key should be renewed immediately for the network security. Some strategies have been proposed to develop the group rekeying protocol, but most of existing schemes are not suitable for sensor networks due to their high overhead and poor scalability. In this paper, we propose a new group rekeying protocol for hierarchical WSNs with renewable network devices. Compared with existing schemes, our rekeying method possesses the following features that are particularly beneficial to the resource-constrained large-scale WSNs: (1) robustness to the node capture attack, (2) reactive rekeying capability to malicious nodes, and (3) low communication and storage overhead.

Multiple hop based routing in homogeneous sensor networks with a single sink suffers performance degradation and severe security threats with the increase of the size of sensor networks. Large-scale sensor networks need to be deployed with multiple powerful nodes as sinks and they should be scheduled to move to different places during the lifetime of the networks. Existing routing mechanisms lack of such supports for large-scale sensor networks. In this paper, we propose a heterogeneous network model where multiple mesh nodes are deployed in a sensor network, and sensed data are collected through two tiers: firstly from a source sensor node to the closest mesh node in a multiple-hop fashion (called sensor routing), and then from the mesh node to the base station through long-distance mesh routing (called mesh routing). Based on this network model, we propose an energy-efficient and secure protocol for the sensor routing that can work well in large-scale sensor networks and resist most of attacks. Experiments demonstrate that our routing protocol significantly reduces average hops for data transmission. Our lightweight security mechanism enables the routing protocol to defend most attacks against sensor networks.