Active Processor Scheduling Using Evolutionary Algorithms

Abstract

The allocation of processes to processors has long been of interest to engineers. The processor allocation problem considered here assigns multiple applications onto a computing system. With this algorithm researchers could more efficiently examine real-time sensor data like that used by United States Air Force digital signal processing efforts or real-time aerosol hazard detection as examined by the Department of Homeland Security. Different choices for the design of a load balancing algorithm are examined in both the problem and algorithm domains. Evolutionary algorithms are used to find near-optimal solutions. These algorithms incorporate multiobjective coevolutionary and parallel principles to create an effective and efficient algorithm for real-world allocation problems. Three evolutionary algorithms (EA) are developed. The primary algorithm generates a solution to the processor allocation problem. This allocation EA is capable of evaluating objectives in both an aggregate single objective and a Pareto multiobjective manner. The other two EAs are designed for fine turning returned allocation EA solutions. One coevolutionary algorithm is used to optimize the parameters of the allocation algorithm. This meta-EA is parallelized using a coarse-grain approach to improve performance. Experiments are conducted that validate the improved effectiveness of the parallelized algorithm. Pareto multiobjective approach is used to optimize both effectiveness and efficiency objectives. The other coevolutionary algorithm generates difficult allocation problems for testing the capabilities of the allocation EA. The effectiveness of both coevolutionary algorithms for optimizing the allocation EA is examined quantitatively using standard statistical methods. Also the allocation EAs objective tradeoffs are analyzed and compared.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2002
Accession Number
ADA413647

Entities

People

  • David J. Caswell

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Cyber
  • Energy and Power Technologies
  • Human Systems

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Computer Programming
  • Computers
  • Control Systems
  • Data Analysis
  • Detection
  • Detectors
  • Digital Signal Processing
  • Engineers
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Genetics
  • High Performance Computing
  • Lymphocytes
  • Signal Processing
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Environmental Impact Assessment (EIA) of Proposed Air Force Base Actions.
  • Parallel and Distributed Computing.