Academic & Scientific Articles

Permanent URI for this communityhttp://dl.cerist.dz/handle/CERIST/3

Browse

Subject: search.filters.subject.GPU

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Fast parallel algorithms for finding elementary circuits of a directed graph: a GPU-based approach
    (Springer Science+Business Media, 2023-03) Benachour, Amira; Yahiaoui, Saïd; El Baz, Didier; Nouali‑Taboudjemat, Nadia; Kheddouci, Hamamache
    Circuits in a graph are interesting structures and identifying them is of an important relevance for many applications. However, enumerating circuits is known to be a difficult problem, since their number can grow exponentially. In this paper, we propose fast parallel approaches for enumerating elementary circuits of directed graphs based on graphics processing unit (GPU). Our algorithms are based on a massive exploration of the graph in a breadth-first search strategy. Algorithm V-FEC explores the graph starting from different vertices simultaneously. To further reduce the search space, we present T-FEC, another algorithm that uses triplets as an initial set to start exploring. To the best of our knowledge, those are the first parallel GPU-based algorithms for finding all circuits of a given graph. In addition, they find circuits of a given length and circuits with a specific vertex or edge. The evaluation results show that the proposed approaches achieve up to 190x speed-up over Johnson’s algorithm, one of the most efficient sequential algorithms for finding circuits.
  • Thumbnail Image
    Item
    New GPU-based Swarm Intelligence Approach For Reducing Big Association Rules Space
    (CERIST, 2017-06-14) Djenouri, Youcef; Bendjoudi, Ahcène; Djenouri, Djamel; Belhadi, Asma; Nouali-Taboudjemat, Nadia
    This paper deals with exploration and mining of association rules in big data, with the big challenge of increasing computation time. We propose a new approach based on meta-rules discovery that gives to the user the summary of the rules’ space through a meta-rules representation. This allows the user to decide about the rules to take and prune. We also adapt a pruning strategy of our previous work to keep only the representatives rules. As the meta-rules space is much larger than the rules space, two approaches are proposed for efficient exploitation. The first one uses a bees swarm optimization method in the meta-rules discovery process, which is extended using GPU-based parallel programming to form the second one. The sequential version has been first tested using medium rules set, and the results show clear improvement in terms of the number of returned meta-rules. The two versions have then been compared on large scale rules sets, and the results illustrate the acceleration on the summarization process by the parallel approach without reducing the quality of resulted meta-rules. Further experiments on Webdocs big data instances reveal that the proposed method of pruning rules by summarizing meta-rules considerably reduces the association rules space compared to state-of-the-art association rules mining-based approaches.