Earticle

The optimization of scheduling problems is based on different criteria to optimize. One of the most important criteria is the minimization of completion time of the last task on the last machine called makespan. In this paper, we present a parallel algorithm for solving the permutation flow shop problem. Our algorithm is a basic parallel distributed algorithm deployed in a grid of computer (Grid’5000). The objective of this work is minimizing the total makespan of the tasks. Our algorithm uses the exact Branch and Bound method to find optimal solutions of the problem through the distribution of the tasks among the available processors. Computational results of our parallel algorithm using well known Taillard’s benchmarks, showed encouraging results. In particular, we succeeded to solve two new instances to optimality which had never been resolved before neither in sequential nor in parallel [29].

Many sorting algorithms have been proposed and implemented in previous years. These algorithms are usually judged by their performance in term of algorithm growth rate according to the input size. Efficient sorting algorithm implementation is important for optimizing the use of other algorithms such as searching algorithms, load balancing algorithms, etc. In this paper, parallel Quicksort, parallel Merge sort, and parallel Merge-Quicksort algorithms are evaluated and compared in terms of the running time, speedup, and parallel efficiency. These sorting algorithms are implemented using Message Passing Interface (MPI) library, and results have been conducted using IMAN1 supercomputer. Results show that the run time of parallel Quicksort algorithm outperforms both Merge sort and Merge-Quicksort algorithms. Moreover, on large number of processors, parallel Quicksort achieves the best parallel efficiency of up to 88%, while Merge sort and Merge-Quicksort algorithms achieve up to 49% and 52% parallel efficiency, respectively.

New performance leaps has been achieved with multiprogramming and multi-core systems. Present parallel programming techniques and environment needs significant changes in programs to accomplish parallelism and also constitute complex, confusing and error-prone constructs and rules. Intel Cilk Plus is a C based computing system that presents a straight forward and well-structured model for the development, verification and analysis of multi-core and parallel programming. In this article, two programs are developed using Intel Cilk Plus. Two sequential sorting programs in C/C++ language are converted to multi-core programs in Intel Cilk Plus framework to achieve parallelism and better performance. Converted program in Cilk Plus is then checked for various conditions using tools of Cilk and after that, comparison of performance and speedup achieved over the single-core sequential program is discussed and reported.

So far, many parallel algorithms have been developed under the assumption that a high performance multicore processor uses a bus for inter-core communications. However, this assumption begins to change as the number of processing cores is increased and thus, higher connectivity among cores is required. So, in this paper, three HEVC intra prediction algorithms are ported into a mesh network-based multicore system by using a wavefront-style parallelization. By analyzing parallel performance, this paper shows that UDIP best fits in the mesh network-based multicore system (almost 2 times faster than other algorithms).

This research is based on the iterative space-marching method for incompressible and compressible Navier-Stokes equations[1-4]. A principle of parallel computational schemes construction for steady and unsteady problems is suggested. It is analytically proven that convergence of these schemes is unconditional for incompressible case. When the parallel scheme is used the total volume of computations is the sum of a large number of independent and equal parts. Estimation of the speed-up K shows that K > 1000 in ideal case. First results of using the parallel schemes are presented.

First, we present two classes of sequential algorithms for minimum flow problem: decreasing path algorithms and preflow algorithms. Then we describe another approach of the minimum flow problem, that consists of applying any maximum flow algorithm in a modified network. In section 5 we present several parallel preflow algorithms that solve the minimum flow problem. Finally, we present an application of the minimum flow problem.

Median 필터는 임계치 분할, 스택킹 특성, 그리고 선형 분리성에 기반하여 이진 영역에서 구현이 가능하다. 본 논문에서는 VLSI 구현에 적합한 변형 가능한 메쉬(RMESH) 구조에서 median 필터링을 위한 1차원 및 2차운 병렬 알고리즘의 성능을 평가한다. 실제로 M 레벨의 1차원 시그널 길이가 N이고 윈도우 폭이 W일 때, 메쉬 구조에서는 $O(Mw^2)$의 시간 복잡도를 갖는 반면 RMESH 구조에서의 알고리즘은 O(Mw) 시간 복잡도를 갖는다. 또한 M 레벨의 2차원 영상의 크기가 $N{\times}N$이고 원도우 크기가 $w{\times}w$라고 가정하면, 본 논문에서 제안한 $N{\times}N$ RMESH 상에서 median 필터링 알고리즘은 $N{\times}N$ 메쉬의 $O(Mw^2)$ 시간 보다 더욱 향상된 O(Mw) 시간에 계산되어진다.

Median filter can be implemented in the binary domain based on threshold decomposition, stacking property, and linear separability. In this paper, we develop one-dimensional and two-dimensional parallel algorithms for the median filter on a reconfigurable mesh with buses(RMESH) which is suitable for VLSI implementation. And we evaluate their performance by comparing the time complexities of RMESH algorithms with those of algorithms on mesh-connected computer. When the length of M-valued 1-D signal is N and w is the window width, the RMESH algorithm is done in O(Mw) time and mesh algorithm is done in $O(Mw^2)$ time. Beside, when the size of M-valued 2-D image is $N{\times}N$ and the window size is $w{\times}w$, our algorithm on $N{\times}N$ RMESH can be computed in O(Mw) time which is a significant improvement over the $O(Mw^2)$ complexity on $N{\times}N$ mesh.

If the distance between two vertices becomes longer after the removal of a vertex u, then u is called a hinge vertex. In this paper, a linear time sequential algorithm is presented to find all hinge vertices of an interval graph. Also, a parallel algorithm is presented which takes O(n/P + log n) time using P processors on an EREW PRAM. AMS Mathematics Subject Classification : 68Q22, 68Q25, 68R10

This research considers scheduling problems with jobs which can be divided into sub-jobs and do not required to be processed immediately following one another. Heuristic algorithms considering how to divide jobs are proposed in an attempt to find near-optimal solutions within reasonable run time. The algorithms contain two phases which are executed recursively. Phase 1 of the algorithm determines how jobs should be divided while phase 2 solves the scheduling problem given the sub-jobs established in phase 1. Simulated annealing and genetic algorithms are applied for the two phases and four heuristic algorithms are established. Numerical experiment is conducted to determine the best parameter values for the heuristic algorithms. Examples with different sizes and levels of complexity are generated. Performance of the proposed algorithms is evaluated. It is shown that the proposed algorithms are able to efficiently and effectively solve the considered problems.

Proposed here is a parallel genetic algorithm accompanied with intermittent migration among subpopulations. It is intended to maintain diversity in the population for a long period . This method was applied to finding out the global maximum of some multimodal functions for which no other methods seem to be useful . Preferable results and their detailed analysis are also presented.

In this paper, we consider the problems of convergence of parallel iterative algorithms for a system of nonlinear variational inequalities and nonexpansive mappings. Strong convergence theorems are established in the frame work of real Banach spaces.

Object tracking is a common task in computer vision, an essential part of various vision-based applications. After several years of development, object tracking in video is still a challenging problem because of various visual properties of objects and surrounding environment. Particle filter is a well-known technique among common approaches, has been proven its effectiveness in dealing with difficulties in object tracking. However, particle filter is a high-complexity algorithms, which is an severe disadvantage because object tracking algorithms are required to run in real time. In this research, we utilize parallel programming to accelerate particle filter-based object tracking algorithms. Experimental results showed that our approach reduced the execution time significantly.

There is a growing demand on remotely sensed and GIS data services in modern society. However, conventional WEB applications based on client/server pattern can not meet the criteria in the future . Grid computing provides a promising resolution for establishing spatial information system toward future applications. Here, a new architecture of the distributed environment for remotely sensed data processing based on the middleware technology was proposed. In addition, in order to utilize the new environment, a problem had to be algorithmically expressed as comprising a set of concurrently executing sub-problems or tasks. Experiment of the algorithm was implemented, and the results show that the new environmental can achieve high speedups for applications compared with conventional implementation.

In parallel job scheduling, each job can be executed simultaneously on multiple machines at a time. Thus in the input instance, a job $J_i$ requires the number $m_i$ of machines on which it shall be processed. The algorithm should determine not only the execution order of jobs but also the machines on which the jobs are executed. In this paper, when the jobs have deadlines, the problem is to maximize the total work of jobs which is completed by their deadlines. The problem is known to be strongly NP-hard [5] and we investigate the approximation algorithms for the problem. We consider a model in which the algorithm can have more machines than the adversary. With this advantage, the problem is how good solution the algorithm can produce against the optimal algorithm.

This paper presents a performance study of two LU decomposition algorithms on two massively parallel SIMD machines: the 16K processor MasPar MP-1 and the 4K processor MasPar MP-2. The paper presents experimental results and an analysis of the algorithms to explain the results. While the blocked and the nonblocked algorithms for LU decomposition have been studied individually by others, we compare the two algorithms and identify the tradeoffs between them. Our analysis of the blocked algorithm shows how the block size affects the interprocessor communication cost and the memory read/write overhead. The analysis in this paper is useful to determine an optimum block size for the blocked algorithm.

This paper considers the parallel machines scheduling problem characterized as a multi-objective combinatorial problem. As this problem belongs to the NP-complete problem, genetic algorithms are applied instead of the traditional analytical approach. The purpose of this study is to show how the problem can be effectively solved by using genetic algorithms with a permutation approach. First, a permutation representation which can effectively represent the chromosome is introduced for this problem . Next, a schedule builder which employs the combination of scheduling theories and a simple heuristic approach is suggested. Finally, through the computer experiments of genetic algorithm to test problems, we show that the niche formation method does not contribute to getting better solutions and that the PMX crossover operator is the best among the selected four recombination operators at least for our problem in terms of both the performance of the solution and the operational convenience.

The parallel-type mechanism provides more accurate and stiff motion than the serial-type mechanism. However, in case of using the haptic device, the performance of the force reflection can be deteriorated due to the singular points existing in workspace. In this paper, we propose a redundantly actuated parallel 3-DOF haptic device, which is singularity-free in the workspace and has an improved force reflection capability. In addition, we propose a new force distribution algorithm, which can reflect force of both high and low resolution, using two sets of actuator with different size. Redundant actuators are attached to the base frame in order to minimize the inertia of the system. Moreover, a wire and gear reduction system is employed to achieve high force reflection along with soft feeling. We confirm the performance of the force reflection capability throughout simulation.