Browse Prior Art Database

A LOAD BALANCING ALGORITHM FOR USE WITH THREE RESOURCES

IP.com Disclosure Number: IPCOM000006758D
Original Publication Date: 1993-Mar-01
Included in the Prior Art Database: 2002-Jan-30
Document File: 5 page(s) / 271K

Publishing Venue

Motorola

Related People

Tom Thomas: AUTHOR [+4]

Abstract

This paper presents an algorithm for balancing resource utilization across three resources in the pres- ence of a dynamic request stream. The algorithm presented has several characteristics which make it an attractive solution to hardware design problems involv- ing allocating three resources to multiple requesters. The algorithm provides a nearly uniform distribution of requests across the resources, requires minimal chip area to implement, provides the resource allocation informa- tion within a small number of gate delays of receiving the requests, and is not complex to implement.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 5

MOTOROLA INC. Technical Developments Volume18 March 1993

A LOAD BALANCING ALGORITHM FOR USE WITH THREE RESOURCES

by Tom Thomas, Mike Shebanow, Mitch Alsup and Keith Witek

INTRODUCTION

  This paper presents an algorithm for balancing resource utilization across three resources in the pres- ence of a dynamic request stream. The algorithm presented has several characteristics which make it an attractive solution to hardware design problems involv- ing allocating three resources to multiple requesters. The algorithm provides a nearly uniform distribution of requests across the resources, requires minimal chip area to implement, provides the resource allocation informa- tion within a small number of gate delays of receiving the requests, and is not complex to implement.

  Section 2 describes the general resource allocation problem. Section 3 presents the proposed load balanc- ing algorithm. Section 4 presents a short discussion of possible variations on the proposed algorithm. In sec- tion 5, an alternative approach is discussed.

THE RESOURCE ALLOCATION PROBLEM

  This section discusses the general resource alloca- tion problem, presents the assumptions made in the devel- opment of the algorithm, and describes the criteria for an optimal solution to the resource allocation problem.

  The general class of problems in which load balanc- ing algorithms are impatant are resource allocation prob- lems. Resource allocation problems involve assigning multiple requesters to multiple resources. The objective of incorporating a load balancing algorithm in a resource allocation mechanism is to enhance the throughput of the system. Resource allocation problems arise in many environments including manofachuing operations, oper- ating systems, and in computer processor hardware. A special case of resource allocation will be discussed in this paper in the context of microprocessor design.

  For the purpose of discussion, several assumptions are made about the characteristics of the resource allo- cation problem. Three assumptions are made about the resources to be allocated. First, it is assumed that the

0 Motorola. Inc. 1993

number of resources in the system is a constant (con- sider the number of hardware resources of a particular type on a microprocessor chip). Second, the resources are assumed to be identical in their capacity to process requests. Third, it is assumed that it is undesirable to stall requesters prior to assigning them to resources. For this reason, each resource is assumed to be capable of buffering pending requests. This mechanism will be referred to as "pending request buffers" in the following discussion.

  Two assumptions are made about the characteris- tics of the requests in the system to be discussed. First, requests in the system are assumed to be indistinguisha- ble from the resource allocator's point of view, but to have different required durations for processing. As an example of this type of situation, consider micropro- cessor se...