Search

Abstract: With the increasing requirement of computation and data amount in embedded multimedia applications, stream architectures are exploited to accelerate the multimedia processing. The increasing arithmetic units on stream architectures make energy consumption a critical metric. In this paper, an energy-efficient stream task scheduling scheme is proposed for embedded multimedia applications on a multi-issued stream architecture. The proposed scheduling scheme takes four steps for task mapping, V/F scaling and record reordering. The target stream application is first mapped to the processor in pipeline to reduce task dependency. Then the supply voltage and frequency of tasks are scaled down for energy reduction by DVFS without violating real-time constraints. The computation intensities of tasks are taken into consideration as the priority for more efficient energy reduction. Besides, when records are dependent, more parallelism is exploited and records are reordered to improve the processing performance. The proposed scheme is evaluated with a set of benchmarks and 14% energy reduction is achieved compared with the GeneS algorithm. [Copyright &y& Elsevier]

Abstract: Due to the advancement of wireless internet and mobile positioning technology, the application of location-based services (LBSs) has become popular for mobile users. Since users have to send their exact locations to obtain the service, it may lead to several privacy threats. To solve this problem, a cloaking method has been proposed to blur users’ exact locations into a cloaked spatial region with a required privacy threshold (k). With the cloaked region, an LBS server can carry out a k-nearest neighbor (k-NN) search algorithm. Some recent studies have proposed methods to search k-nearest POIs while protecting a user’s privacy. However, they have at least one major problem, such as inefficiency on query processing or low precision of retrieved result. To resolve these problems, in this paper, we propose a novel k-NN query processing algorithm for a cloaking region to satisfy both requirements of fast query processing time and high precision of the retrieved result. To achieve fast query processing time, we propose a new pruning technique based on a 2D-coodinate scheme. In addition, we make use of a Voronoi diagram for retrieving the nearest POIs efficiently. To satisfy the requirement of high precision of the retrieved result, we guarantee that our k-NN query processing algorithm always contains the exact set of k nearest neighbors. Our performance analysis shows that our algorithm achieves better performance in terms of query processing time and the number of candidate POIs compared with other algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we focus on the semi-partitioned scheduling of sporadic tasks with constrained deadlines and identical processors. We study two cases of semi-partitioning: (i) the case where the worst case execution time (WCET) of a job can be portioned, each portion being executed on a dedicated processor, according to a static pattern of migration; (ii) the case where the jobs of a task are released on a processor, 1 time out of p, where p is an integer at most equal to the number of processors, according to a round-robin migration pattern. The first approach has been investigated in the state-of-the-art by migrating a job at its local deadline, computed from the deadline of the task it belongs to. We study several local deadline assignment heuristics (fair, based on processor utilization and based on the minimum acceptable local deadline for a job on a processor). In both cases, we propose feasibility conditions for the schedulability of sporadic tasks scheduled using earliest deadline first (EDF) semi-partitioned scheduling. We show that the load function used for global scheduling to establish the feasibility of sporadic task sets exhibits interesting properties in the semi-partitioning context. We carry out simulations to study the performance of the two approaches in terms of success rate and number of migrations, for platforms composed of four and eight processors. We compare the performance of these semi-partitioned heuristics with the performance of classical partitioned scheduling algorithms and with a global scheduling heuristic which is currently considered to have good performances. [Copyright &y& Elsevier]