Academic & Scientific Articles
Permanent URI for this communityhttp://dl.cerist.dz/handle/CERIST/3
Browse
9 results
Search Results
Item GPU-based Bio-inspired Model for Solving Association Rules Mining Problem(CERIST, 2017-03-06) Djenouri, Youcef; Bendjoudi, Ahcène; Djenouri, Djamel; Commuzi, Marcoproblem with the purpose of extracting the correlations between items in sizeable data instances. According to the state of the art, the bio-inspired approaches proved their usefulness by finding high number of satisfied rules in a reasonable time when dealing with medium size instances. These approaches are unsuitable for large databases and especially for those existing on the web such as the Webdocs instance. Recently, the Graphics Processor Units (GPU) is considered as one of the most used parallel hardware to solve large scientific complex problems. In this paper, we propose a new GPU-based model of the bio-inspired approaches for solving association rules mining problem. Our model benefits from the massively GPU threaded by evaluating multiple rules in parallel on GPU. To validate the proposed model, the most used bio-inspired approaches (GA, PSO, and BSO) have been executed on GPU to solve well-known large ARM instances. Real experiments have been carried out on an Intel Xeon 64 bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that the genetic algorithm outperforms PSO and BSO. Moreover, it outperforms the state-of-the-art GPU-based ARM approaches when dealing with the challenging Webdocs instance.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, NadiaIn 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.Item Data reordering for minimizing threads divergence in GPU-based evaluating association rules(CERIST, 2015-03-26) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Habbas, Zineb; Nouali-Taboudjemat, NadiaThis last decade, the success of Graphics Processor Units (GPUs) has led researchers to launch a lot of works on solving large complex problems by using these cheap and powerful architecture. Association Rules Mining (ARM) is one of these hard problems requiring a lot of computational resources. Due to the exponential increase of data bases size, existing algorithms for ARM problem become more and more inefficient. Thus, research has been focusing on parallelizing these algorithms. Recently, GPUs are starting to be used to this task. However, their major drawback is the threads divergence problem. To deal with this issue, we propose in this paper an intelligent strategy called Transactions- based Reordering "TR" allowing an efficient evaluation of association rules on GPU by minimizing threads divergence. This strategy is based on data base re-organization. To validate our proposition, theoretical and experimental studies have been carried out using well-known synthetic data sets. The results are very promising in terms of minimizing the number of threads divergence.Item Data reordering for minimizing threads divergence in GPU-based evaluating association rules(2015-06) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Habbas, Zineb; Nouali-Taboudjemat, NadiaThis last decade, the success of Graphics Processor Units (GPUs) has led researchers to launch a lot of works on solving large complex problems by using these cheap and powerful architecture. Association Rules Mining (ARM) is one of these hard problems requiring a lot of computational resources. Due to the exponential increase of data bases size, existing algorithms for ARM problem become more and more inefficient.Thus, research has been focusing on parallelizing these algorithms. Recently, GPUs are starting to be used to this task. However, their major drawback is the threads divergence problem. To deal with this issue, we propose in this paper an intelligent strategy called transactions-based Reordering ”TR” allowing an efficient evaluation of association rules on GPU by minimizing threads divergence. This strategy is based on data base re-organization. To validate our proposition, theoretical and experimental studies have been carried out using well-known synthetic datasets. The results are very promising in terms of minimizing the number of threads divergence.Item GPU-based Bees Swarm Optimization for Association Rules Mining(Springer, 2014) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, ZinebAssociation Rules Mining (ARM) is a well-known combinatorial optimization problem aiming at extracting relevant rules from given large scale data sets. According to the state of the art, the bio-inspired methods proved their efficiency by generating acceptable solutions in a reasonable time when dealing with small and medium size instances. Unfortunately, to cope with large instances such as the webdocs benchmark, these methods require more and more powerful processors and are time expensive. Nowadays, computing power is no longer a real issue. It can be provided by the power of emerging technologies such as GPUs that are massively multi-threaded processors. In this paper, we investigate the use of GPUs to speed up the computation. We propose two GPU-based bees swarm algorithms for association rules mining (SE-GPU and ME-GPU). SE-GPU aims at evaluating one rule at a time where each thread is associated with one transaction, whereas ME-GPU evaluates multiple rules in parallel on GPU where each thread is associated with several transactions. To validate our approaches, the two algorithms have been executed to solve well-known large ARM instances. Real experiments have been carried out on an Intel Xeon 64 bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our approaches improve the execution time up to x100 over the sequential mono-core BSO-ARM algorithm. Moreover, the proposed approaches have been compared with CPU multi-core ones (1 to 8 cores). The results show that they are faster than the multi-core versions what ever the number of used cores.Item Parallel Association Rules Mining Using GPUs and Bees Behaviors(CERIST, 2014-06-24) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, ZinebThis paper addresses the problem of association rules mining with large data sets using bees behaviors. The bees swarm optimization method have been successfully applied on small and medium data size. Nevertheless, when dealing Webdocs benchmark (the largest benchmark on the web), it is bluntly blocked after more than 15 days. Additionally, Graphic processor Units are massively threaded providing highly intensive computing and very usable by the optimization research community. The parallelization of such method on GPU architecture can be deal large data sets as the case of WebDocs in real time. In this paper, the evaluation process of the solutions is parallelized. Experimental results reveal that the suggested method outperforms the sequential version at the order of ×100 in most data sets, furthermore, the WebDocs benchmark is handled with less than ten hours.Item Parallel Rules Mining Using GPUs and Bees Behaviors(2014-08) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, ZinebThis paper addresses the problem of association rules mining with large data sets using bees behaviors. The bees swarm optimization method have been successfully applied on small and medium data size. Nevertheless, when dealing Webdocs benchmark (the largest benchmark on the web), it is bluntly blocked after more than 15 days. Additionally, Graphic processor Units are massively threaded providing highly intensive computing and very usable by the optimization research community. The parallelization of such method on GPU architecture can be deal large data sets as the case of WebDocs in real time. In this paper, the evaluation process of the solutions is parallelized. Experimental results reveal that the suggested method outperforms the sequential version at the order of ×100 in most data sets, furthermore, the WebDocs benchmark is handled with less than ten hours.Item Parallel B&B Algorithm for Hybrid Multi-core/GPU Architectures(CERIST, 2013) Bendjoudi, Ahcène; Mehdi, MalikaB&B algorithms are well known techniques for exact solving of combinatorial optimization problems. They perform an implicit enumeration of the search space instead of exhaustive one. Based on a pruning technique, they reduce considerably the computation time required to explore the whole search space. Nevertheless, these algorithms remain inefficient when dealing with large combinatorial optimization instances. They are time-intensive and they require a huge computing power to be solved optimally. Nowadays, multi-core-based processors and GPU accelerators are often coupled together to achieve impressive performances. However, classical B&B algorithms must be rethought to deal with their two divergent architectures. In this paper, we propose a new B&B approach exploiting both the multi-core aspect of actual processors and GPU accelerators. The proposed approaches have been executed to solve FSP instances that are well-known combinatorial optimization benchmarks. Real experiments have been carried out on an Intel Xeon 64-bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our hybrid B&B approach speeds up the execution time up to x123 over the sequential mono-core B&B algorithm.Item GPU-accelerated Bounding for Branch-and-Bound applied to a Permutation Problem using Data Access Optimization(John Wiley & Sons, 2013-11) Melab, Nouredine; Chakroun, Imen; Bendjoudi, AhcèneBranch-and-Bound (B\&B) algorithms are attractive methods for solving to optimality combinatorial optimization problems using an implicit enumeration of a dynamically built tree-based search space. Nevertheless, they are time-consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow-Shop scheduling problem (FSP) have shown that the bounding operation consumes over $98\%$ of the execution time of the B\&B algorithm. In this paper, we investigate the use of GPU computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization. Extensive experiments have been carried out on well-known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU-based single core execution using an Intel Core i7-970 processor without GPU, speedups higher than $100$ times faster are achieved for large problem instances. At an equivalent peak performance, GPU-accelerated B\&B is twice faster than its multi-core counterpart.