Accession Number:

ADA059390

Title:

Evaluation of the Bitstring Algorithm

Descriptive Note:

Interim rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1978-04-12

Pagination or Media Count:

40.0

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-1140E and the resulting performance improvement relative to the assembly code implementation are discussed.

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE