Immunological Approaches to Load Balancing in MIMD Systems James J. Clark

2025-05-08 0 0 1.67MB 17 页 10玖币

侵权投诉

Immunological Approaches to Load Balancing in

MIMD Systems

James J. Clark

Department of Electrical and Computer Engineering

and Centre for Intelligent Machines

McGill University

October 5, 2022

Abstract

Eﬀective utilization of Multiple-Instruction-Multiple-Data (MIMD) parallel computers re-

quires the application of good load balancing techniques. In this paper we show that heuristics

derived from observation of complex natural systems, such as the mammalian immune system,

can lead to eﬀective load balancing strategies. In particular, the immune system processes of

regulation, suppression, tolerance, and memory are seen to be powerful load balancing mech-

anisms.

We provide a detailed example of our approach applied to parallelization of an image

processing task, that of extracting the circuit design from the images of the layers of a CMOS

integrated circuit. The results of this experiment show that good speedup characteristics can

be obtained when using immune system derived load balancing strategies.

1 Introduction

In the quest for increased rates of computation computer scientists and engineers have turned

toward parallel computing systems. Such systems speed computational tasks by dividing the task

into parts and executing each part in parallel with separate computational engines. Early parallel

computers were of the Single-Instruction-Multiple-Data (SIMD) form [8], wherein each processing

element executes the same computations on diﬀerent data. The eﬀectiveness of these types of

parallel computers are limited by the extent to which an arbitrary task can be divided into a set

of identical sub-tasks. There are many problems which are easily partitioned in this manner, for

example image ﬁltering and other tasks which involve the application of local operations repeatedly

over a ﬁeld of data. The large majority of computational tasks, however, are very diﬃcult to

partition into sets of identical sub-tasks. Implementing these tasks in SIMD computers will result

in a very ineﬃcient use of computational resources.

A more general and powerful class of parallel computers are the Multiple-Instruction-Multiple-

Data computers [8]. These computers consist of a set of processing elements that can execute

diﬀerent computations on diﬀerent data. The ﬂexibilty added by the capability of the processors

to execute independent programs permits a much wider range of tasks to be eﬃciently parallelized

than is the case for SIMD systems. A completely general MIMD system, one which allows its con-

stituent processing elements to perform any computation whatsoever and to access whatever data

it requires, presents an intractable programming or speciﬁcation problem. The space of possible

programs is vast compared with a SIMD system, and lacks suitable structure to permit ﬁnding the

optimal set of programs for a given task. Typically, the intractability of MIMD programming is

attacked by applying constraints, usually architectural, to the space of possible programs. These

constraints reduce the space of the possible programs, and also provide a template to guide the

programmer in the speciﬁcation of a program for a given task.

Besides the diﬃculty in constraining the programming, developers of algorithms to be imple-

mented on MIMD machines are faced with another diﬃcult problem, that of load balancing. In any

arXiv:2210.01222v1 [cs.DC] 3 Oct 2022

multi-processor system the most important measure of performance is the speedup in completing

a given task obtained by using a number of processors over using a single processor. If a processor

is performing non-useful work (i.e. work not relevant to solving the problem at hand), or is dupli-

cating relevant work being done by another processor, then it is not contributing to speeding up

the task. It is clear that what needs to be done in order to achieve the maximum possible speedup

is to distribute the workload amongst the processors as evenly as possible. This process is called

load balancing, and is one of the most important facets of MIMD system design [2].

One can make the observation that many natural systems, such as the mammalian immune

system, can be thought of as MIMD systems. These natural systems have been “programmed”

by evolution to carry out many types of tasks and provide examples of eﬃcient algorithms that

can be adapted to other MIMD systems that exhibit similar characteristics. Others have made

this observation before (e.g. Paton [19]), but have emphasised the use of computational metaphors

and models in forming biological models. We want to turn this around, and concentrate on the

application of biological metaphors and models in specifying computational processes. Speciﬁcally,

we are interested in abstracting the “load balancing” strategies that are in eﬀect being employed by

these natural systems. Primary amongst these strategies are the regulatory processes that play a

crucial role in immune system function. We will also examine the role that other immune processes

such as immunological memory have to play in load balancing.

We end the paper with an application of our approach to the parallelization of an image

processing task, that of extracting an electrical circuit netlist from images of the IC fabrication

process masks. This problem is diﬃcult to parallelize due to the many serial sub-problems that

must be solved. In spite of this, our approach yields respectable speedup performance. The

population dynamics that arise in these simulations are clearly similar to those in immune systems

and illustrate the action of the various load balancing strategies that are in use.

1.1 Load Balancing in the Immune System

Load balancing is one of the most important and diﬃcult aspects of programming of MIMD

computers. In brief, it is the allocation of resources amongst the active elements of the system in a

way which leads to the fastest execution of the task at hand. We propose to approach the problem

of load balancing by using insights gained from observing natural systems, such as the immune

system.

The immune system [11, 15] is a massively parallel MIMD system. It consists of about 1010

cells, each of which have diﬀerent roles to play in its functioning. The immune system has evolved to

respond eﬀectively and quickly to appropriate stimuli, and to make eﬃcient use of its constituents.

Thus it is a good example from which to abstract principles of eﬀective load balancing.

Some of the primary attributes of the immune system are:

•Recognition of environmental conditions

•Tolerance to irrelevant conditions

•Response speedup through immunological memory

•Response regulation

•Dynamic cell population control

•Message passing via a shared environment

One important lesson we can learn from the immune system with respect to load balancing

is that cellular populations are dynamic, and populations of a given cell type are increased or

decreased only when appropriate conditions are detected. These conditions are either signaled

directly, through sensing of environmental factors (such as presence of antigens) or indirectly

through messages sent by other cells. Likewise, load balancing schemes are classiﬁed as being

either static or dynamic. In static load balancing, the schedule of tasks that a given agent will

perform is speciﬁed before execution begins. This requires detailed a priori knowledge about

the characteristics of the tasks needed in the course of executing the application. If the precise

nature of the application is not known beforehand, static schedules will generally be non-optimal.

Dynamic load balancing is a form of load balancing that is more eﬃcient in the face of incomplete

a priori information about task characteristics. In dynamic load balancing, the assignment of

tasks to processors (or agents) is done based on the current state of the system. Clearly, any load

balancing scheme based on the immune system metaphor will be dynamic.

Let us now examine each of the attributes of the immune system listed above and discuss their

application to load balancing.

The recognition capability of the immune system is a common requirement of computational

tasks. It is often the case that a program must carry out one or more searches for a given pattern.

In addition, the task usually requires that some action be carried out once the search has found

a target. In itself, recognition is not a process which serves load balancing ends. Rather, it

is a process which must itself be a target of load balancing processes. Nonetheless, recognition

processes, by their essentially parallel nature, put constraints on the load balancing processes. In

general, speeds for search operations scale linearly with the number of units engaged in the search,

and the immune system is no diﬀerent in this regard. This does not mean, however, that the

optimal strategy is to employ all resources in the search activity and to redirect all these resources

to other activities once the target has been found. The system must be able to respond quickly to

unknown conditions, and assignment of all system resources to a given task may slow response to

some events.

Tolerance of “self-antigens” is crucial in the immune system, as otherwise the immune system

would attack everything in the body, and not limit itself to external invaders. In load balancing,

tolerance can be viewed as limiting irrelevant processing. That is, there may be environmental

conditions which signal or suggest that a certain computation should be done, but a computation

which does not contribute to the task being carried out. In this case the environmental condition,

or its signal, should be ignored, or tolerated, by the system. In the context of load balancing in

MIMD systems, the symptoms of the analog to an autoimmune disease would be the slowing down

of the rate in which problems are solved.

In the immune system tolerance is produced in a number of ways. The most well known is

that of clonal deletion, wherein a T-cell responsive to a self-antigen is killed in the thymus if it has

responded. This happens early in life, so there is a chance that self-antigens which appear later in

life (e.g. during puberty) will cause immune responses. For these case, the so-called peripheral T

cell tolerance mechanisms come into play. In peripheral tolerance, auto-immune responsive cells are

not killed but instead inactivated, a process referred to as anergy [15]. It is thought that anergy

results from a lack of proper co-stimulation of the cell. In co-stimulation, the presence of the

self-antigen must coincide with the presentation of B7 membrane proteins by Antigen Presenting

Cells (APCs) if there is to be an eﬀective response. Anergy may also be caused if a variant form

of the antigen is encountered. Instead of anergy, tolerance can be mediated by suppression from

other lymphocytes (called suppressor T-cells). The mechanisms by which suppressor T-cells are

activated are similar to those thought to induce anergy. Anergy is not irreversible. The cytokine

IL-2 can cause anergic T cells to become reactivated.

The immune system employs a number of strategies for optimizing response speeds. One of

these is immunological memory [16]. When a given condition is ﬁrst encountered, an eﬀective

response to it may be slow in occuring. If a small number of units are henceforth dedicated to

detecting this speciﬁc condition, then future responses may be much faster. This is actually a load

balancing strategy as it dictates that a small number of agents be assigned to carry out a seemingly

irrelevant task in the hope that a rapid response can be attained when environmental conditions

change appropriately. In the immune system T-cells can either be “eﬀector cells”, capable of taking

direct action against invaders, or “memory cells”. A recent theory of T-cell genesis [7] holds that

low antigen levels can cause young, naive, T-cells to become memory cells instead of eﬀector cells.

In this case, then, environmental conditions can determine the function of a given agent. Another

theory [16] holds that eﬀector T-cells become memory cells after a certain number of cell divisions.

In load balancing terms, this approach is saying that a T-cell that has undergone many divisions

in the past has done so in reponse to relevant environmental conditions, which are likely to arise

again in the future, even if they are currently not present.

An important way in which responses can be sped up is to use positive feedback. In the

immune system T4 “helper” cells stimulate themselves to reproduce through release of chemical

messages (proteins known as cytokines). Because of this positive feedback, the population of T4

cells can increase very rapidly. Unchecked, however, the positive feedback would cause the T4 cell

population to grow until resources become used up. This feedback is limited somewhat by the fact

that the cytokines typically have a short lifespan. Another way to prevent such a runaway is to

provide a counteracting negative feedback. One does not want this negative feedback to simply

cancel out the positive feedback, otherwise no speedup would be attained. A way out of this

dilemma is to delay the negative feedback. This is done in the immune system with a two stage

regulatory process, in which the T4 cells facilitate increases in the population of T8 (cytotoxic)

cells which then suppress the population of T4 helper cells. The suppression does not become

signiﬁcant until the T8 population grows, however, leading to a delay in the response suppression.

In this way, a rapid response is assured, but one which does not run away.

Two-stage regulation can also be used to choose between possible responses, by suppressing the

inappropriate (or irrelevant) responses. In the immune system, two classes of helper cells, Th1 and

Th2 operate in this fashion [10]. The immune system has two basic approaches to deal with an

invading antigen. The ﬁrst is a humoral, or antibody-mediated immunity (AMI) which is eﬀective

against extracellular antigens. It is triggered by the presence of antibodies againts a particular anti-

gen. The other is cell-mediated immunity (CMI) which is eﬀective against intracellular antigens.

It is triggered by cytokines (chemical messengers) released by various immune system cells, such as

macrophages. A stressed macrophage releases the cytokine IL12 which, in combination with IL2

enhances Th1 production. Th1 cells in turn secrete IFN- which suppresses Th2 production. This

shifts the balance of the immune system towards a CMI response. On the other hand, antigen

stimulated B-cells secrete the cytokine IL10 which, in conjunction with IL4, suppresses Th1 cells

(through inhibition of secretion of IL12 by macrophages). Th2 cells also secrete IL4 which further

inhibits Th1 production. In this way the immune system is directed towards a humoral response.

As noted by Abbas et al, T-cells select one of multiple modes of reactivity, and the immunological

“self” is not deﬁned by the repertoire of T-cell types, but rather by the behaviour of the system

in response to environmental conditions.

1.2 Redundancy and Irrelevancy Minimization

Our goal is to abstract from the functioning of the immune system various principles which can

be used in developing load balancing strategies for MIMD systems.

To this end, we propose that load balancing in the immune system (and in complex natural

systems in general) is best thought of in terms of as a process for minimizing agent redundancy

and irrelevancy. Redundancy refers to the condition wherein an agent is duplicating work being

performed by another agent. Redundancy is a problem when there a large number of agents in a

region compared with the number needed to carry out a task. One must be careful to correctly

determine this number. For example, in searching for an object randomly placed in a region, the

more agents that are employed, the sooner the search will be completed. Once the object has

been found, however, an eﬀector operation may only require a few agents. Hence redundancy is

a problem for the eﬀector operation, whereas it was not a problem for the search task. In the

immune system most tasks, such as detection and elimination of antigen, are essentially parallel in

nature, so redundancy resolution is not so important as in some other complex systems.

Irrelevancy, on the other hand, refers to the condition wherein an agent is performing work

which is not contributing anything to the overall task of the system. Irrelevancy is a problem when

there are a small to moderate number of agents relative to the number required to carry out a

task.

We propose that general load balancing strategies should aim to minimize both redundancy

and irrelevancy. Such load balancing strategies will neccessarily involve both the detection and

correction of redundancy and irrelevance. Redundancy will usually be easy to detect, merely by

the presence of other agents performing the same tasks. The major problem is to determine whether

or not these other agents are actually neccessary, as in the case of a parallel task such as search.

Some techniques for detecting and alleviating redundancy that are found in nature (and in the

immune system) are:

•Dominance The dominant agent gets to perform a certain activity while other agents are

inhibited from doing so. The dominance can be based on ﬁxed agent characteristics, such as

an identiﬁcation code, or can be based on variable agent attributes, such as age, time spent

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ImmunologicalApproachestoLoadBalancinginMIMDSystemsJamesJ.ClarkDepartmentofElectricalandComputerEngineeringandCentreforIntelligentMachinesMcGillUniversityOctober5,2022AbstractEectiveutilizationofMultiple-Instruction-Multiple-Data(MIMD)parallelcomputersre-quirestheapplicationofgoodloadbalancingtechn...

展开>> 收起<<

Immunological Approaches to Load Balancing in MIMD Systems James J. Clark.pdf

共17页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Immunological Approaches to Load Balancing in MIMD Systems James J. Clark

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: