The Experts below are selected from a list of 14913 Experts worldwide ranked by ideXlab platform

Alok Choudhary - One of the best experts on this subject based on the ideXlab platform.

  • a new parallel algorithm for two pass connected component labeling
    International Parallel and Distributed Processing Symposium, 2014
    Co-Authors: Siddharth Gupta, Diana Palsetia, Md Shahadath Hossain Patwary, Ankit Agrawal, Alok Choudhary
    Abstract:

    Connected Component Labeling (CCL) is one of the most important step in pattern recognition and image processing. It assigns labels to the pixels such that adjacent pixels sharing the same features are assigned the same label. Typically, CCL requires several passes over the data. We focus on two-pass technique where each pixel is given a provisional label in the first pass whereas an actual label is assigned in the second pass. We present a scalable parallel two-pass CCL algorithm, called PAREMSP, which employs a scan strategy and the best union-find technique called REMSP, which uses REM'S algorithm for storing label equivalence information of pixels in a 2-D image. In the first pass, we divide the image among threads and each thread runs the scan phase along with REMSP simultaneously. In the second phase, we assign the final labels to the pixels. As REMSP is easily parallelizable, we use the parallel version of REMSP for merging the pixels on the boundary. Our experiments show the scalability of PAREMSP achieving speedups up to 20.1 using 24 cores on Shared Memory Architecture using OpenMP for an image of size 465.20 MB. We find that our proposed parallel algorithm achieves linear scaling for a large resolution fixed problem size as the number of processing elements are increased. Additionally, the parallel algorithm does not make use of any hardware specific routines, and thus is highly portable.

  • A new parallel algorithm for two-pass connected component labeling
    Proceedings of the International Parallel and Distributed Processing Symposium IPDPS, 2014
    Co-Authors: Siddharth Gupta, Diana Palsetia, Md Shahadath Hossain Patwary, Ankit Agrawal, Alok Choudhary
    Abstract:

    Connected Component Labeling (CCL) is an important step in pattern recognition and image processing. It assigns labels to the pixels such that adjacent pixels sharing the same features are assigned the same label. Typically, CCL requires several passes over the data. We focus on two-pass technique where each pixel is given a provisional label in the first pass whereas an actual label is assigned in the second pass. We present a scalable parallel two-pass CCL algorithm, called PAREMSP, which employs a scan strategy and the best union-find technique called REMSP, which uses REM's algorithm for storing label equivalence information of pixels in a 2-D image. In the first pass, we divide the image among threads and each thread runs the scan phase along with REMSP simultaneously. In the second phase, we assign the final labels to the pixels. As REMSP is easily parallelizable, we use the parallel version of REMSP for merging the pixels on the boundary. Our experiments show the scalability of PAREMSP achieving speedups up to $20.1$ using $24$ cores on Shared Memory Architecture using OpenMP for an image of size $465.20$ MB. We find that our proposed parallel algorithm achieves linear scaling for a large resolution fixed problem size as the number of processing elements are increased. Additionally, the parallel algorithm does not make use of any hardware specific routines, and thus is highly portable.

  • A new scalable parallel DBSCAN algorithm using the disjoint-set data structure
    International Conference for High Performance Computing Networking Storage and Analysis SC, 2012
    Co-Authors: Md Shahadath Hossain Patwary, Diana Palsetia, Wei-keng Liao, Fredrik Manne, Ankit Agrawal, Alok Choudhary
    Abstract:

    DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of Dbscan is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel Dbscan algorithm (Pdsdbscan) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of Dbscan. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for Shared and for distributed Memory. Using data sets containing up to several hundred million high-dimensional points, we show that Pdsdbscan significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on Shared Memory Architecture, and speedups up to 5,765 using 8,192 cores on distributed Memory Architecture.

Howard Barringer - One of the best experts on this subject based on the ideXlab platform.

  • CTL^* model checking on a Shared-Memory Architecture
    Formal Methods in System Design, 2006
    Co-Authors: Cornelia P. Inggs, Howard Barringer
    Abstract:

    In this article we present the parallelisation of an explicit-state CTL^* model checking algorithm for a virtual Shared-Memory high-performance parallel machine Architecture. The algorithm uses a combination of private and Shared data structures for implicit and dynamic load balancing with minimal synchronisation overhead. The performance of the algorithm and the impact that different design decisions have on the performance are analysed using both mathematical cost models and experimental results. The analysis shows not only the practicality and effective speedup of the algorithm, but also the main pitfalls of parallelising model checking for Shared-Memory Architectures.

  • ctl model checking on a Shared Memory Architecture
    Electronic Notes in Theoretical Computer Science, 2005
    Co-Authors: Cornelia P. Inggs, Howard Barringer
    Abstract:

    In this paper we present a parallel algorithm for CTL* model checking on a virtual Shared-Memory high-performance parallel machine Architecture. The algorithm is automata-driven and follows a games approach where one player wins if the automaton is empty while the other player wins if the automaton is nonempty. We show how this game can be played in parallel using a dynamic load balancing technique to divide the work across the processors. The practicality and effective speedup of the algorithm is illustrated by performance graphs.

  • effective state exploration for model checking on a Shared Memory Architecture
    Electronic Notes in Theoretical Computer Science, 2002
    Co-Authors: Cornelia P. Inggs, Howard Barringer
    Abstract:

    Abstract In this paper we present results from experimental studies investigating implementation strategies for explicit-state temporal-logic model checking on a virtual Shared-Memory high-performance parallel machine Architecture. In particular, a parallel state exploration algorithm using a two-queue structure for load balancing is proposed and its performance analysed at the hand of experimental studies. We then discuss implementation issues for parallel automata-theoretic model checking using this parallel state exploration algorithm.

Md Shahadath Hossain Patwary - One of the best experts on this subject based on the ideXlab platform.

  • a new parallel algorithm for two pass connected component labeling
    International Parallel and Distributed Processing Symposium, 2014
    Co-Authors: Siddharth Gupta, Diana Palsetia, Md Shahadath Hossain Patwary, Ankit Agrawal, Alok Choudhary
    Abstract:

    Connected Component Labeling (CCL) is one of the most important step in pattern recognition and image processing. It assigns labels to the pixels such that adjacent pixels sharing the same features are assigned the same label. Typically, CCL requires several passes over the data. We focus on two-pass technique where each pixel is given a provisional label in the first pass whereas an actual label is assigned in the second pass. We present a scalable parallel two-pass CCL algorithm, called PAREMSP, which employs a scan strategy and the best union-find technique called REMSP, which uses REM'S algorithm for storing label equivalence information of pixels in a 2-D image. In the first pass, we divide the image among threads and each thread runs the scan phase along with REMSP simultaneously. In the second phase, we assign the final labels to the pixels. As REMSP is easily parallelizable, we use the parallel version of REMSP for merging the pixels on the boundary. Our experiments show the scalability of PAREMSP achieving speedups up to 20.1 using 24 cores on Shared Memory Architecture using OpenMP for an image of size 465.20 MB. We find that our proposed parallel algorithm achieves linear scaling for a large resolution fixed problem size as the number of processing elements are increased. Additionally, the parallel algorithm does not make use of any hardware specific routines, and thus is highly portable.

  • A new parallel algorithm for two-pass connected component labeling
    Proceedings of the International Parallel and Distributed Processing Symposium IPDPS, 2014
    Co-Authors: Siddharth Gupta, Diana Palsetia, Md Shahadath Hossain Patwary, Ankit Agrawal, Alok Choudhary
    Abstract:

    Connected Component Labeling (CCL) is an important step in pattern recognition and image processing. It assigns labels to the pixels such that adjacent pixels sharing the same features are assigned the same label. Typically, CCL requires several passes over the data. We focus on two-pass technique where each pixel is given a provisional label in the first pass whereas an actual label is assigned in the second pass. We present a scalable parallel two-pass CCL algorithm, called PAREMSP, which employs a scan strategy and the best union-find technique called REMSP, which uses REM's algorithm for storing label equivalence information of pixels in a 2-D image. In the first pass, we divide the image among threads and each thread runs the scan phase along with REMSP simultaneously. In the second phase, we assign the final labels to the pixels. As REMSP is easily parallelizable, we use the parallel version of REMSP for merging the pixels on the boundary. Our experiments show the scalability of PAREMSP achieving speedups up to $20.1$ using $24$ cores on Shared Memory Architecture using OpenMP for an image of size $465.20$ MB. We find that our proposed parallel algorithm achieves linear scaling for a large resolution fixed problem size as the number of processing elements are increased. Additionally, the parallel algorithm does not make use of any hardware specific routines, and thus is highly portable.

  • A new scalable parallel DBSCAN algorithm using the disjoint-set data structure
    International Conference for High Performance Computing Networking Storage and Analysis SC, 2012
    Co-Authors: Md Shahadath Hossain Patwary, Diana Palsetia, Wei-keng Liao, Fredrik Manne, Ankit Agrawal, Alok Choudhary
    Abstract:

    DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of Dbscan is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel Dbscan algorithm (Pdsdbscan) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of Dbscan. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for Shared and for distributed Memory. Using data sets containing up to several hundred million high-dimensional points, we show that Pdsdbscan significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on Shared Memory Architecture, and speedups up to 5,765 using 8,192 cores on distributed Memory Architecture.

Cornelia P. Inggs - One of the best experts on this subject based on the ideXlab platform.

  • CTL^* model checking on a Shared-Memory Architecture
    Formal Methods in System Design, 2006
    Co-Authors: Cornelia P. Inggs, Howard Barringer
    Abstract:

    In this article we present the parallelisation of an explicit-state CTL^* model checking algorithm for a virtual Shared-Memory high-performance parallel machine Architecture. The algorithm uses a combination of private and Shared data structures for implicit and dynamic load balancing with minimal synchronisation overhead. The performance of the algorithm and the impact that different design decisions have on the performance are analysed using both mathematical cost models and experimental results. The analysis shows not only the practicality and effective speedup of the algorithm, but also the main pitfalls of parallelising model checking for Shared-Memory Architectures.

  • ctl model checking on a Shared Memory Architecture
    Electronic Notes in Theoretical Computer Science, 2005
    Co-Authors: Cornelia P. Inggs, Howard Barringer
    Abstract:

    In this paper we present a parallel algorithm for CTL* model checking on a virtual Shared-Memory high-performance parallel machine Architecture. The algorithm is automata-driven and follows a games approach where one player wins if the automaton is empty while the other player wins if the automaton is nonempty. We show how this game can be played in parallel using a dynamic load balancing technique to divide the work across the processors. The practicality and effective speedup of the algorithm is illustrated by performance graphs.

  • effective state exploration for model checking on a Shared Memory Architecture
    Electronic Notes in Theoretical Computer Science, 2002
    Co-Authors: Cornelia P. Inggs, Howard Barringer
    Abstract:

    Abstract In this paper we present results from experimental studies investigating implementation strategies for explicit-state temporal-logic model checking on a virtual Shared-Memory high-performance parallel machine Architecture. In particular, a parallel state exploration algorithm using a two-queue structure for load balancing is proposed and its performance analysed at the hand of experimental studies. We then discuss implementation issues for parallel automata-theoretic model checking using this parallel state exploration algorithm.

Ankit Agrawal - One of the best experts on this subject based on the ideXlab platform.

  • a new parallel algorithm for two pass connected component labeling
    International Parallel and Distributed Processing Symposium, 2014
    Co-Authors: Siddharth Gupta, Diana Palsetia, Md Shahadath Hossain Patwary, Ankit Agrawal, Alok Choudhary
    Abstract:

    Connected Component Labeling (CCL) is one of the most important step in pattern recognition and image processing. It assigns labels to the pixels such that adjacent pixels sharing the same features are assigned the same label. Typically, CCL requires several passes over the data. We focus on two-pass technique where each pixel is given a provisional label in the first pass whereas an actual label is assigned in the second pass. We present a scalable parallel two-pass CCL algorithm, called PAREMSP, which employs a scan strategy and the best union-find technique called REMSP, which uses REM'S algorithm for storing label equivalence information of pixels in a 2-D image. In the first pass, we divide the image among threads and each thread runs the scan phase along with REMSP simultaneously. In the second phase, we assign the final labels to the pixels. As REMSP is easily parallelizable, we use the parallel version of REMSP for merging the pixels on the boundary. Our experiments show the scalability of PAREMSP achieving speedups up to 20.1 using 24 cores on Shared Memory Architecture using OpenMP for an image of size 465.20 MB. We find that our proposed parallel algorithm achieves linear scaling for a large resolution fixed problem size as the number of processing elements are increased. Additionally, the parallel algorithm does not make use of any hardware specific routines, and thus is highly portable.

  • A new parallel algorithm for two-pass connected component labeling
    Proceedings of the International Parallel and Distributed Processing Symposium IPDPS, 2014
    Co-Authors: Siddharth Gupta, Diana Palsetia, Md Shahadath Hossain Patwary, Ankit Agrawal, Alok Choudhary
    Abstract:

    Connected Component Labeling (CCL) is an important step in pattern recognition and image processing. It assigns labels to the pixels such that adjacent pixels sharing the same features are assigned the same label. Typically, CCL requires several passes over the data. We focus on two-pass technique where each pixel is given a provisional label in the first pass whereas an actual label is assigned in the second pass. We present a scalable parallel two-pass CCL algorithm, called PAREMSP, which employs a scan strategy and the best union-find technique called REMSP, which uses REM's algorithm for storing label equivalence information of pixels in a 2-D image. In the first pass, we divide the image among threads and each thread runs the scan phase along with REMSP simultaneously. In the second phase, we assign the final labels to the pixels. As REMSP is easily parallelizable, we use the parallel version of REMSP for merging the pixels on the boundary. Our experiments show the scalability of PAREMSP achieving speedups up to $20.1$ using $24$ cores on Shared Memory Architecture using OpenMP for an image of size $465.20$ MB. We find that our proposed parallel algorithm achieves linear scaling for a large resolution fixed problem size as the number of processing elements are increased. Additionally, the parallel algorithm does not make use of any hardware specific routines, and thus is highly portable.

  • A new scalable parallel DBSCAN algorithm using the disjoint-set data structure
    International Conference for High Performance Computing Networking Storage and Analysis SC, 2012
    Co-Authors: Md Shahadath Hossain Patwary, Diana Palsetia, Wei-keng Liao, Fredrik Manne, Ankit Agrawal, Alok Choudhary
    Abstract:

    DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of Dbscan is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel Dbscan algorithm (Pdsdbscan) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of Dbscan. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for Shared and for distributed Memory. Using data sets containing up to several hundred million high-dimensional points, we show that Pdsdbscan significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on Shared Memory Architecture, and speedups up to 5,765 using 8,192 cores on distributed Memory Architecture.