ABSTRACT:
Distributed real-time and embedded (DRE) systems can be composed of hundreds of software components running across tens or hundreds of networked processors that are physically separated from one another. A key concern in DRE systems is determining the spatial deployment topology, which is how the software components map to the underlying hardware components.
Optimizations, such as placing software components with high-frequency communications on processors that are closer together, can yield a number of important benefits, such as reduced power consumption due to decreased wireless transmission power required to communicate between the processing nodes.
Determining a spatial deployment plan across a series of processors that will minimize power consumption is hard since the spatial deployment plan must respect a combination of real-time scheduling, fault-tolerance, resource, and other complex constraints. This paper presents a hybrid heuristic/evolutionary algorithm, called ScatterD, for automatically generating spatial deployment plans that minimize power consumption.
This work provides the following contributions to the study of spatial deployment optimization for power consumption minimization:
(1) it combines heuristic bin-packing with an evolutionary algorithm to produce a hybrid algorithm with excellent deployment derivation capabilities and scalability.
(2) it shows how a unique representation of the spatial deployment solution space integrates the heuristic and evolutionary algorithms.
(3) it analyzes the results of experiments performed with data derived from a large-scale avionics system that compares ScatterD with other automated deployment techniques. These results show that ScatterD reduces power consumption by between 6% and 240% more than standard bin-packing, genetic, and particle swarm optimization algorithms.
A FRACTIONATED SPACECRAFT CASE STUDY
This section presents a case study of a weather satellite designed using a fractionated spacecraft architecture. We use this case study throughout the paper to motivate the challenges of devising complex spatial deployment plans.
A Fractionated Spacecraft Spatial Deployment Problem.
Overview of Fractionated Spacecraft:
The fractionated spacecraft weather satellite is controlled by a ground station. The satellite runs a set of software components (such as Image Acquisition for capturing weather images, Feature identification for identifying important characteristics of the images, and Feature Reporting for relaying image information to a ground station) that is dictated by the ground control station.
Spatial Deployment Challenges for DRE Systems:
A deployment topology is a mapping of software components and their associated tasks to a hardware processor components. In real-time systems, either fixed priority scheduling algorithms, such as rate monotonic (RM) scheduling , or dynamic priority scheduling algorithms, such as earliest-deadline-first (EDF), control the execution ordering of the individual tasks on the processors.
A Software Deployment Topology for the Fractionated Spacecraft.
Challenge 1: Accounting for Variations in Performance Per Watt of Processing Cores:
Current deployment techniques, such as bin-packing, are designed to minimize the number of computational nodes that are utilized by a deployment topology, but do not provide assurance or optimization of the power consumed by the deployment topology. The goal of solving a bin-packing problem is to take a set of items with varying sizes and pack them into a series of limited size bins using as few bins as possible. Properties of the power consumption of the bins are not considered in the problem.
Challenge 2: Handling Variations in Network Link Power Consumption:
A key determinant of power consumption in DRE systems with mobile ad-hoc networks is radio transmission for wireless network links. The power consumption of a wireless link is directly related to the transmit power required to propagate the transmission over the physical area separating the computational nodes and the frequency that the network link is in use.
Challenge 3: Deployment Automation Technique Scalability:
A fundamental constraint of deriving deployment topologies for DRE systems is that all software components must meet their real-time deadlines on the processors to which they are deployed. This basic constraint is known as the multi-processor scheduling problem and has been shown to be NP-Hard. Since the problem is NP-Hard, many optimization algorithms with exponential time-complexity a rehard to apply.
THE SCATTERD DEPLOYMENT ALGORITHM
This section describes ScatterD, which is a hybrid heuristic / evolutionary algorithm for optimizing spatial deployment topologies for minimizing power consumption. ScatterD allows DRE system developers to automatically derive deployment topologies that meet a combination of real-time scheduling, memory, co-location, and spatial constraints. This section first presents a formal model of spatial deployment for power consumption minimization and then provides an overview of evolutionary algorithms.
EMPIRICAL RESULTS
This section analyzes empirical results obtained by applying the ScatterD techniques, bin acking, PSO, and a genetic algorithm to an example fractionated spacecraft system. The fractionated spacecraft example was produced by modifying a production avionics dataset obtained from Lockheed Martin Aeronautics through the SPRUCE project (www.sprucecommunity.org), which is a web accessible portal that pairs academic researchers with industry challenge problems complete with representative project data.
Homogeneous Xenon Deployment.
CONCLUDING REMARKS AND LESSONS LEARNED
Power consumption in DRE systems can be minimized by carefully choosing a good spatial deployment topology. The spatial deployment topology determines how farapart communicating software components are and thus how much transmit power is needed for wireless communication. Moreover, processing nodes vary in performance per watt for different tasks and these variations can be exploited to optimize the energy consumption footprint of the system.
- Power consumption can be reduced significantly by carefully balancing network utilization and processor efficiency tradeoffs. The empirical data from Section 4 showed that accounting for both network and processor power consumption provides superior results to focusing exclusively on either one individually.
- Solution space representation is critical to the ability of an evolutionary algorithm to efficiently generatespatial deployment topologies. By modeling the solution space as permutations of the input to a heuristic bin-packing algorithm, we observed a roughly four-fold increase in the number of good deployment topologies that were explored.
- Combining heuristic and evolutionary algorithms over comes a number of problems of applying either independently to spatial deployment topology derivation. For example, by combining first-fit bin-packing with PSO, a hybrid algorithm can be created that has a lower probability of generating invalid solutions during the evolutionary solution permutation process.
- Determining the appropriate method of integrating heuristic and evolutionary algorithms is not easy,significant experimentation is required to find a way of integrating the two techniques that yields good results. For example, preliminary experiments that we performed that used evolutionary techniques to adjust the relative weights of bin-packing items did not perform nearly as well as modeling the solution space as packing-order vectors.
- Other combinations of heuristic and evolutionary algorithms may provide superior results. Each heuristic algorithm has unique problem characteristics for which it produces excellent results. In future work, therefore, we plan to investigate other combinations of heuristic and evolutionary algorithms that perform well on spatial deployment optimization problems.
Source: Vanderbilt University
Authors: Jules White | Brian Dougherty | Chris Thompson | Douglas C . Schmidt
>> B.Com CA Final Year Projects