17819894
Bus-Based Parallel Computers: A Viable Way for Massive Parallelism
In most distributed memory MIMD multiprocessors, processors are connected by a point-to-point interconnection network. Since interprocessor communication frequently constitutes serious bottlenecks, several architectures were proposed that enhance point-to-point topologies with the help of multiple bus systems so as to improve the communication efficiency. In this paper we study global communication on parallel architectures where the communication means are constituted solely by busses. We focus on the hyperpath and the hypergrid architectures, which are the bus-based versions of the well used point-to-point linear and grid interconnection networks. Using (hyper) graph theoretic concepts in order to model inter-processor communication in such networks, we developed a new tool called simplification in order to give extremely efficient algorithms for gossiping (all-to-all or total exchange communications).
2233122
New Techniques for Cycle Shrinking
Several loop transformations techniques have been designed to extract parallelism from nested loop structures. We first review two important approaches, known as Generalized Cycle Shrinking presented by Shang, O'Keefe and Fortes and the Index Shift Method introduced by Liu, Ho and Sheu. The main result of the paper is a new methodology that permits to combine cycle shrinking techniques with the index shift method. We present a new optimization method that produces the best scheduling vector, and we show that we can outperform previous results by an arbitrary speedup factor.
52830861
A Coarse-Grained Parallel Algorithm for Maximal Cliques in Circle Graphs
We present a parallel algorithm for generating the maximal cliques of a circle graph with n vertices and m edges. We consider the Coarse-Grained Multicomputer Model (CGM) and show that the proposed algorithm requires O(log p) communication rounds, where p is the number of processors, independent of n. The main contribution is the use of a new technique based on the unrestricted depth search for the design of CGM algorithms.
14651264
Computing Maximum Subsequence in Parallel
The maximum subsequence problem finds the contiguous subsequence of n real numbers with the highest sum. This is an important problem that arises in several contexts in Computational Biology in the analysis of DNA or protein sequences. The maximum subsequence problem of n given scores can be solved sequentially in O(n) time. In this paper we present an efficient BSP/CGM parallel algorithm that requires a constant number of communication rounds. In the proposed algorithm, the input is partitioned equally among the processors and the sequence stored on each processor is reduced to only five numbers. This reduction is crucial as it allows all the resulting values to be concentrated on a single processor which runs an adaptation of the sequential algorithm to obtain the result. The amount of data transmitted is 5p where p is the number of processors, thus independent of the input size n. The good performance of the parallel algorithm is confirmed by experimental results run on a 64-node Beowulf parallel computer, giving almost linear speedup. Topic of interest: Algorithms and Software Tools for Computational Molecular Biology
13919002
Efficient embeddings into the hypercube using matrix transformations
The embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embedding the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes novel methods, based on matrix transformations, for e~ciently embedding different networks into the hypercube (binary n-cube). First, we use this method to embed r-ary m-cubes into a binary n-cube of the same size with dilation 1. While our method has the same dilation as traditional methods using rejlected Gray code, it has the additional property of making the layout of the binary n-cube more suitable for divide-and-conquer algorithms. Second, we use our matrix transformation method to optimally embed hierarchical interconnection networks into the binary n-cube which we would not achieve using rejlected Gray code embedding. Thus, this embedding method has signi$cant practical importance in enhancing the capabilities of the hypercube..
41930759
Embedding Hierarchical Hypercube Networks into the Hypercube
The embedding of one interconnection network into another is a very important issue in the design and analysis of parallel algorithms. Through such embeddings, the algorithms originally developed for one architecture can be directly mapped to another architecture. This paper describes a new embedding method, based on matrix transformations, for optimally embedding hierarchical hypercube networks (HHNs) into the hypercube (binary n-cube). Thus, this embedding method has practical importance in enhancing the capabilities and extending the usefulness of the hypercube, since hierarchical hypercube networks have proven to be very cost-effective for a wide range of applications.
6926758
Semantic Correlation Network Based Text Clustering
Text documents have sparse data spaces, and nearest neighbors may belong to different classes when using current existing proximity measures to describe the correlation of documents. In this paper, we propose an asymmetric similarity measure to strengthen the discriminative feature of document objects. We construct a semantic correlation network by asymmetric similarity between documents and conjecture the power law feature of the connections distributions. Hub points which exist in semantic correlation network are classified by an agglomerative hierarchical clustering approach named SCN. Both objects similarity and neighbors similarity are considered in the definition of hub points proximity. Finally, we assign the rest text objects to their nearest hub points. The experimental evaluation on textual data sets demonstrates the validity and efficiency of SCN. The comparison with other clustering algorithms shows the superiority of our approach.
2193712
Similarity Joins of Text with Incomplete Information Formats
Similarity join over text is important in text retrieval and query. Due to the incomplete formats of information representation, such as abbreviation and short word, similarity joins should address an asymmetric feature that these incomplete formats may contain only partial information of their original representation. Current approaches, including cosine similarity with q-grams, can hardly deal with the asymmetric feature of similarity between words and their incomplete formats. In order to find this type of incomplete format information with asymmetric features, we develop a new similarity join algorithm, namely IJoin. A novel matching scheme is proposed to identify the overlap between two entities with incomplete formats. Other than q-grams, we reconnect the sequence of words in a string to reserve the abbreviated information. Based on the asymmetric features of similar entities with incomplete formats, we adopt a new similarity function. Furthermore, an efficient algorithm is implemented by using the join operation in SQL, which reduces pairs of tuples in similarity comparison. The experimental evaluation demonstrates the effectiveness and the efficiency of our approach.
17783880
TCUAP: A Novel Approach of Text Clustering Using Asymmetric Proximity
Text documents have sparse data spaces and current existing methods of text clustering use symmetry proximity to measure the correlation of documents. In this paper, we propose a novel approach to strengthen the discriminative feature of document objects, which uses asymmetric proximity for text clustering. We present a measure of asymmetric proximity between documents and between clusters. TCUAP is an agglomerative hierarchical clustering algorithm and carries on the clustering analysis by strong components of sparse matrix. The experimental evaluation on textual data sets demonstrates the validity and efficiency of our approach. The result shows that the measure of asymmetric proximity possesses higher accuracy than that of symmetry proximity.
701055
Practical Security Improvement of PKCS#5
A public key infrastructure (PKI) is being deployed in a field of network security. PKCS#5 is one of the most popular standards in PKI framework, intended for the practical implementation of password-based cryptography. So, the PKCS#5 encryption must be useful for general software applications within multimedia systems. However, it has a critical weak point in terms of security such as being vulnerable to off-line attacks due to the password-derived encryption key. In this paper, we observe a practical and simple method to improve security of the PKCS#5 encryption without modifying the installed base. The idea is to hide a salt by exploiting several existing schemes.