Browsing by Author "Dabah, Adel"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    Accelerated Search over Encrypted Cloud Data
    (IEEE, 2017-02-13) Boucenna, Fateh; Nouali, Omar; Dabah, Adel; Kechid, Samir
    Companies and other organizations such as hospitals seek more and more to enjoy the benefits of cloud computingin terms of storage space and computing power. However, outsourced data must be encrypted in order to be protected againstpossible attacks. Therefore, traditional information retrieval systems (IRS) are no longer effective and must be adapted in order towork over encrypted cloud data. In addition, in order to providethe ability to search over an encrypted index, we use the vectormodel to represent documents and queries which is the most usedin the literature. During the search process, the query vectormust be compared with each document vector which is a time consuming process since the data collection is generally huge.Consequently, the search performance is degraded and the searchprocess is too slow. To overcome this drawback, we proposethe use of High Performance Computing (HPC) architecturesto accelerate the search over encrypted cloud data. Indeed,we propose several techniques that take benefit from Graphics Processing Unit (GPU) and computer cluster architectures by distributing the work between different threads. In addition,in order to get the best performance, we design our solutionsso that they can process several queries simultaneously. Theexperimental study using 400.000 documents demonstrates theefficiency of our proposals by reaching a speed-up around 46x.
  • Thumbnail Image
    Item
    Efficient approximate approach for graph edit distance problem
    (Elsevier, 2021-11) Dabah, Adel; Chegrane, Ibrahim; Yahiaoui, Saïd
    Graph Edit Distance (GED) problem is a well-known tool used to measure the similarity/dissimilarity between two graphs. It searches for the best set of edit operations (in terms of cost) that transforms one graph into another. Due to the NP-hardness nature of the problem, the search space increases exponentially making exact approaches impossible to use for large graphs. In this context, there is a huge need for approaches that give near-optimal results in reasonable time. In this paper, we propose a tree-based approximate approach for dealing with GED problem. It operates on a search tree that models all possible solutions of the problem. Since exploring the whole tree is impractical; this approach keeps only the best nodes at each level of the tree for further exploration. This reduces enormously the execution time without scarifying the solution quality. Experiments using small and medium size data-sets show the low deviation of our results as compared to the optimal results of a Depth First Search algorithm. Moreover, our approach show a strong scalability potential by dealing with large data-sets in low execution time.
  • Thumbnail Image
    Item
    Efficient parallel B&B method for the Blocking Job Shop Scheduling Problem
    (2016-07) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, Abdelhakim
    The blocking job shop scheduling problem (BJSS) is a version of the classical job shop scheduling with no intermediate buffer between machines. It is known to be NP-hard in the strong sense. The major drawbacks of the previous works are the huge time needed to explore the search space and the low ratio of feasible to explored solutions when applying metaheuristics, leading to a poor quality of final solutions. In order to accelerate the exploration of the search space and overcome the drawback of metaheuristics, we propose in this paper a parallel Branch and Bound (B&B) algorithm to act both as an exact or approximate methods. The proposed parallel B&B approach is based on the master-worker paradigm, exploiting the computing power offered by cluster architectures. The master performs a breadth-first exploration to ensure high availability of tasks (sub-problems) while the workers perform a depth-first exploration in order to browse a large number of feasible solutions, therefore, obtaining a faster improvement of the solution quality. The proposed approach has been executed on a cluster based architecture using 32 nodes with 16 CPU cores each. The obtained results show a good speedup of the execution time with 80% efficiency. We have been able to solve optimally ten BJSS benchmark instances never solved before. Moreover, our proposed approach improved the best solutions for more than 22 benchmark instances.
  • Thumbnail Image
    Item
    Efficient parallel branch-and-bound approaches for exact graph edit distance problem
    (Elsevier, 2022-12) Dabah, Adel; Chegrane, Ibrahim; Yahiaoui, Saïd; Bendjoudi, Ahcene
    Graph Edit Distance (GED) is a well-known measure used in the graph matching to measure the similarity/dissimilarity between two graphs by computing the minimum cost of edit operations needed to transform one graph into another. This process, Which appears to be simple, is known NP-hard and time consuming since the search space is increasing exponentially. One way to optimally solve this problem is by using Branch and Bound (B&B) algorithms, Which reduce the computation time required to explore the whole search space by performing an implicit enumeration of the search space instead of an exhaustive one based on a pruning technique. nevertheless, They remain inefficient when dealing with large problem instances due to the impractical running time needed to explore the whole search space. To overcome this issue, We propose in this paper three parallel B&B approaches based on shared memory to exploit the multi-core CPU processors: First, a work-stealing approach where several instances of the B&B algorithm explore a single search tree concurrently achieving speedups up to 24 faster than the sequential version. Second, a tree-based approach where multiple parts of the search tree are explored simultaneously by independent B&B instances achieving speedups up to 28. Finally, Due to the irregular nature of the GED problem, two load-balancing strategies are proposed to ensure a fair workload between parallel processes achieving impressive speedups up to 300. all experiments have been carried out on well-known datasets
  • Thumbnail Image
    Item
    GPU parallel B&B for the Blocking job shop scheduling problem.
    (CERIST, 2016-02-22) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, Abdelhakim; El Baz, Didier
    Branch and bound algorithms (B&B) are well known techniques for solving optimally combinatorial optimization problems. Nevertheless, these algorithms remain inefficient when dealing with large instances. This paper deals with the blocking job shop scheduling (BJSS), which is a version of classical job shop scheduling with no intermediate buffer between machines. This problem is an NP-hard problem and its exact resolution using the sequential approach is impractical. We propose in this paper a GPU-based parallelization in which a two level scheme is used. The first level is a node-based parallelization in which the bounding process is faster because it is calculated in parallel using several threads organized in one GPU block. To fully occupy the GPU, we propose a second level of parallelization which is a generalization of the first level. Therefore, for each iteration several search tree nodes are evaluated on the GPU using several thread-blocks. The obtained results, using the well-known Taillard instances, confirm the efficiency of the proposed approach. Also, the results show that our approach is 65 times faster than an optimized sequential B&B version.
  • Thumbnail Image
    Item
    Multi and Many-core Parallel B&B approaches for the Blocking Job Shop Scheduling Problem
    (2016-07) Dabah, Adel; Bendjoudi, Ahcène; Ait Zai, Abdelhakim; El Baz, Didier; Nouali-Taboudjemat, Nadia
    In this paper, we propose three approaches to accelerate the B&B execution time using Multi and Many-core systems to solve the NP-hard Blocking Job Shop Scheduling problem (BJSS). The first approach is based on Master/Worker paradigm where the workers independently explore the branches sent by the master. The second approach is a node-based parallelization that does not change the design of the B&B algorithm, except that the bounding process is faster since it is calculated in parallel using several threads organized in one GPU block. The third approach is a Multi-Core CPU/GPU hybridization that benefits from the power of both the CPU-cores and the GPU at the same time. This hybridization is based on concurrent kernels execution provided by Nvidia Multi process Service (MPS) i.e. each host process (Master or Worker) launches his own kernel to accelerate the bounding process on GPU. The obtained results using Taillard instances confirm the efficiency of our proposals. The first two approaches are respectively three and eighteen times faster compared to the sequential version. The results of the hybrid approach show a relative speedup over ninety times as compared to the sequential approach and therefore prove the advantage of using both the CPU-cores and the GPU at the same time.