Evaluation of the Bitstring Algorithm

Abstract

A resource allocation technique based on an alternative data representation to the list structure, i.e. the bitvector, is discussed in this paper. The data structure provides for implicit collapsing of available resources, and the algorithm, called Bitstring, can be applied to any type of resource without performance loss. An optimized implementationof Bitstring is compared with a corresponding list structure algorithm (Firstfit). Two bitvector algorithms for special resource allocation environments, Exactstring and Quickstring, are presented. The implementation of Bitstring in microcode on a PDP-11/40E and the resulting performance improvement relative to the assembly code implementation are discussed.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 12, 1978
Accession Number
ADA059390

Entities

People

  • Peter Feiler

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Advanced Electronics
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Computer Science
  • Computers
  • Instruction Set Architecture
  • Instructions
  • Lists (Data Structures)
  • Machines
  • Microcode
  • Numbers
  • Operating Systems
  • Resource Management
  • Scientific Research
  • Sequences
  • Simulations
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Parallel and Distributed Computing.