AIRCC's International Journal of Computer Science and Information Technology

R. Kalpana ¹, P. Thambidurai ²

Affiliations
1 Department of Computer Science and Engineering, Pondicherry Engineering College, Puducherry, IN
2 Perunthalaivar Kamarajar Institute of Engineering and Technology, Karaikal, Puducherry, IN

Abstract

The Dijkstra's algorithm is applied in many real world problems like mobile routing, road maps, railway networks, etc,. There are many techniques available to speedup the algorithm while guaranteeing the optimality of the solution. Almost all of the speedup techniques have a substantial amount of parallelism that can be exploited to decrease its running time. By suitably modifying portions of the existing system various degrees of parallelism can be achieved. The rapidly growing field of multiprocessing systems and multi-core processors provide many opportunities for such improvements. In these techniques there's always a demand for the running time and the time required for pre-processing. Space requirements for the pre-processing also have a major influence on the running time of the algorithm.

The main focus of the work is to implement landmark technique and to identify the segment of the code in landmark pre-processing which can be parallelized to obtain better speedup. The results are applied to the combined speedup technique which is based on landmarks and containers. The experimental results were compared and analysed for determining better performance improvements in random graphs and planar graphs.

Keywords

Dijkstra's Algorithm, Graph Theory, Parallel Execution, Speed-Up.

Full Text

   

Santhi Baskaran ¹, P. Thambidurai ²

Affiliations
1 Department of Information Technology, Pondicherry Engineering College, Puducherry, IN
2 Department of Computer Science and Engineering, Pondicherry Engineering College, Puducherry, IN

Abstract

Energy consumption is a critical design issue in real-time systems, especially in battery- operated systems. Maintaining high performance, while extending the battery life between charges is an interesting challenge for system designers. Dynamic Voltage Scaling (DVS) allows a processor to dynamically change speed and voltage at run time, thereby saving energy by spreading run cycles into idle time. Knowing when to use full power and when not, requires the cooperation of the operating system scheduler. Usually, higher processor voltage and frequency leads to higher system throughput while energy reduction can be obtained using lower voltage and frequency. Instead of lowering processor voltage and frequency as much as possible, energy efficient real-time scheduling adjusts voltage and frequency according to some optimization criteria, such as low energy consumption or high throughput, while it meets the timing constraints of the real-time tasks. As the quantity and functional complexity of battery powered portable devices continues to raise, energy efficient design of such devices has become increasingly important. Many real-time scheduling algorithms have been developed recently to reduce energy consumption in the portable devices that use DVS capable processors. Extensive power aware scheduling techniques have been published for energy reduction, but most of them have been focused solely on reducing the processor energy consumption. While the processor is one of the major power hungry units in the system, other peripherals such as network interface card, memory banks, disks also consume significant amount of power. Dynamic Power Down (DPD) technique is used to reduce energy consumption by shutting down the processing unit and peripheral devices, when the system is idle. Three algorithms namely Red Tasks Only (RTO), Blue When Possible (BWP) and Red as Late as Possible (RLP) are proposed in the literature to schedule the real-time tasks in Weakly-hard real-time systems. This paper proposes optimal slack management algorithms to make the above existing weakly hard real-time scheduling algorithms energy efficient using DVS and DPD techniques.

Keywords

Weakly-Hard Real-Time System, Skippable Periodic Task, Energy Efficient Scheduling, DVS, DPD.

Full Text