Optimal Partitioning and Granularity of Uniform Task Graphs

Task partitioning is an important technique in parallel processing.In this paper,we investigate the optimal partitioning strategies and granularities of tasks with communications based on several models of parallel computer systems.Different from the usual approach,we study the optimal partitioning strategies and granularities from the viewpoint of minimizing T as well as minimizing NT^2,where N is the number of processors used and T is the program execution time using N processors.Our results show that the optimal partitioning strategies for all cases discussed in this paper are the same--either to assign all tasks to one processor or to distribute them among the processors as equally as possible depending only on the functions of ratio of running time to communication time R/C.     

Distributing and Scheduling Divisible Task on Parallel Communicating Processors

In this paper we propose a novel scheme for scheduling divisible task on parallel processors connected by system interconnection network with arbitrary topology,The divisible task is a computation that can be divided into arbitrary independent subtasks solved in parallel.Our model takes into consideration communication initial time and communication delays between processors.Moreover,by constructing the corresponding Network Spanning present the concept of Balanced Task Distribution Tree and use it to design the Equation Set Creation Algorithm in which the set of linear equations is created by traversing the NST in Post-order.After solving the created equations,we get the optimal task assignment scheme.Experiments confirm the applicability of our scheme in real-life situations.     

Optimal Partitioning and Granularity of Uniform Task Graphs

Task partitioning is an important technique in parallel processing.In this paper,we investigate theoptimal partitioning strategies and granularities of tasks with communications based on several models ofparallel computer systems.Different from the usual approach,we study the optimal partitioning strate-gies and granularities from the viewpoint of minimizing T as well as minimizing NT~2,where N is thenumber of processors used and T is the program execution time using N processors.Our results showthat the optimal partitioning strategies for all cases discussed in this paper are the same——either to as-sign all tasks to one processor or to distribute them among the processors as equally as possible de-pending only on the functions of ratio of running time to communication time R/C.     

An accelerated K-means clustering algorithm using selection and erasure rules

The K-means method is a well-known clustering algorithm with an extensive range of applications,such as biological classification,disease analysis,data mining,and image compression.However,the plain K-means method is not fast when the number of clusters or the number of data points becomes large.A modified K-means algorithm was presented by Fahim et al.(2006).The modified algorithm produced clusters whose mean square error was very similar to that of the plain K-means,but the execution time was shorter.In this study,we try to further increase its speed.There are two rules in our method:a selection rule,used to acquire a good candidate as the initial center to be checked,and an erasure rule,used to delete one or many unqualified centers each time a specified condition is satisfied.Our clustering results are identical to those of Fahim et al.(2006).However,our method further cuts computation time when the number of clusters increases.The mathematical reasoning used in our design is included.     

Checkpoint Management with Double Modular Redundancy Based on the Probability of Task Completion

This paper proposes a checkpoint rollback strategy for real-time systems with double modular redundancy.Without built-in fault-detection and spare processors,our scheme is able to recover from both transient and permanent faults.Two comparisons are conducted at each checkpoint.First,the states stored in two consecutive checkpoints of one processor are compared for checking integrity of the processor.The states of two processors are also compared for detecting faults and the system rolls back to the previous checkpoint whenever required by logic of the proposed scheme.A Markov model is induced by the fault recovery scheme and analyzed to provide the probability of task completion within its deadline.The optimal number of checkpoints is selected so as to maximize the probability of task completion.     

A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid

Efficient task scheduling is critical to achieving high performance on grid computing environment. The task scheduling on grid is studied as optimization problem in this paper. A heuristic task scheduling algorithm satisfying resources load balancing on grid environment is presented. The algorithm schedules tasks by employing mean load based on task predictive execution time as heuristic information to obtain an initial scheduling strategy. Then an optimal scheduling strategy is achieved by selecting two machines satisfying condition to change their loads via reassigning their tasks under the heuristic of their mean load. Methods of selecting machines and tasks are given in this paper to increase the throughput of the system and reduce the total waiting time. The efficiency of the algorithm is analyzed and the performance of the proposed algorithm is evaluated via extensive simulation experiments. Experimental results show that the heuristic algorithm performs significantly to ensure high load balancing and achieve an optimal scheduling strategy almost all the time. Furthermore, results show that our algorithm is high efficient in terms of time complexity.     

Fault-Tolerant Scheduling for Real-Time Embedded Control Systems

With the increasing complexity of industrial application, an embedded control system (ECS) requires processing a number of hard real-time tasks and needs fault-tolerance to assure high reliability. Considering the characteristics of real-time tasks in ECS, an integrated algorithm is proposed to schedule real-time tasks and to guarantee that all real-time tasks are completed before their deadlines even in the presence of faults. Based on the nonpreemptive critical-section protocol (NCSP), this paper analyzes the blocking time introduced by resource conflicts of relevancy tasks in fault-tolerant multiprocessor systems. An extended schedulability condition is presented to check the assignment feasibility of a given task to a processor. A primary/backup approach and on-line replacement of failed processors are used to tolerate processor failures. The analysis reveals that the integrated algorithm bounds the blocking time, requires limited overhead on the number of processors, and still assures good processor utilization. This is also demonstrated by simulation results. Both analysis and simulation show the effectiveness of the proposed algorithm in ECS.     

Energy Efficiency of a Multi-Core Processor by Tag Reduction

We consider the energy saving problem for caches on a multi-core processor.In the previous research on low power processors,there are various methods to reduce power dissipation.Tag reduction is one of them.This paper extends the tag reduction technique on a single-core processor to a multi-core processor and investigates the potential of energy saving for multi-core processors.We formulate our approach as an equivalent problem which is to find an assignment of the whole instruction pages in the physical memory to a set of cores such that the tag-reduction conflicts for each core can be mostly avoided or reduced.We then propose three algorithms using different heuristics for this assignment problem.We provide convincing experimental results by collecting experimental data from a real operating system instead of the traditional way using a processor simulator that cannot simulate operating system functions and the full memory hierarchy.Experimental results show that our proposed algorithms can save total energy up to 83.93% on an 8-core processor and 76.16% on a 4-core processor in average compared to the one that the tag-reduction is not used for.They also significantly outperform the tag reduction based algorithm on a single-core processor.     

SVM-based ontology matching approach

There are a lot of heterogeneous ontologies in semantic web, and the task of ontology mapping is to find their semantic relationship. There are integrated methods that only simply combine the similarity values which are used in current multi-strategy ontology mapping. The semantic information is not included in them and a lot of manual intervention is also needed, so it leads to that some factual mapping relations are missed. Addressing this issue, the work presented in this paper puts forward an ontology matching approach, which uses multi-strategy mapping technique to carry on similarity iterative computation and explores both linguistic and structural similarity. Our approach takes different similarities into one whole, as a similarity cube. By cutting operation, similarity vectors are obtained, which form the similarity space, and by this way, mapping discovery can be converted into binary classification. Support vector machine (SVM) has good generalization ability and can obtain best compromise between complexity of model and learning capability when solving small samples and the nonlinear problem. Because of the said reason, we employ SVM in our approach. For making full use of the information of ontology, our implementation and experimental results used a common dataset to demonstrate the effectiveness of the mapping approach. It ensures the recall ration while improving the quality of mapping results.     

Image decomposing for inpainting using compressed sensing in DCT domain

Inpainting images with occlusion or corruption is a challenging task. Most existing algorithms are pixel based, which construct a statistical model from image features. However, in these algorithms, the frequency component is not sufficiently addressed. In this paper, we propose a novel algorithm that utilizes compressed sensing （CS） in frequency domain to reconstruct corrupted images. In order to reconstruct image, we first decompose the image into two functions with different basic characteristics - structure component and textual component. We seek a sparse representation for the functions and use the DCT coefficients of this representation to generate an over-complete dictionary. Experimental results on real world datasets demonstrate the efficacy of our method in image inpainting. We compare our method with three state-of-the-art inpalnting algorithms and demonstrate its advantages in terms of both quantitative and qualitative aspects.