Report on CPU Coalition Formation
Xin Li, Juan Luo
April, 16, 2002
1. Identify the related names with CPU
In the new class AgentCPU which is similar to AgentRTSS, add the following attributes:
_currentCPUAlloc the current CPU amount allocated to an agent
_currentCPUUsage the current CPU usage of an agent
_cpuAlloc the new CPU allocation after getting from other agents
In the ProfCoalCpu class, add the following attributes:
_cpuNeeded the CPU amount needed from other agents
if (_currentCPUUsage > _currentCPUAlloc)
_cpuNeeded = _currentCPUUsage - _currentCPUAlloc
if (_currentCPUUsage <= _ currentCPUAlloc)
_cpuNeeded = 0
_cpuRequested the CPU amount actually requested from other agents
_cpuRequested = _cpuNeeded + _cpuMaxConsumed
_cpuMaxConsumed the CPU amount consumed during forming coalition
2. The object to which CPU is allocated
In RTSS system environment, the final object to which the CPU resource is allocated is each thread in each agent. In the simulation environment, however, the final object to which the CPU resource is allocated is each agent.
3. Simulator
In current, the single simulator (or called random number generator or coordinator) is not used. Since its main purpose is to generate a set of random numbers whose sum is not greater than 66% and to do the initial coalition formation stage. In fact, only at the beginning it is necessary to generate such a set of numbers to get each _currentCPUAlloc. After that, _currentCPUAlloc can be derived from _cpuAlloc. So it does not need to be randomly generated any more. Even at the beginning, we can set a fixed number for each agent as the first _currentCPUAlloc value.
_currentCPUUsage must be a number not greater than the corresponding _currentCPUAlloc. If it is greater than _currentCPUAlloc, the agent needs to seek help from other agents. We can get this value by analyzing the current workload, i.e., the number of tasks.
_currentCPUUsage = ( ) r
Each agent will keep checking current CPU usage, _currentCPUUsage. If _currentCPUUsage <= _currentCPUAlloc, then _currentCPUAlloc keeps unchanged. Otherwise, the agent begins to negotiate with other agents to get more CPU. After negotiation, its _currentCPUAlloc is assigned to be _cpuAlloc.
4. Initial coalition formation stage
In current, when agent A wants more CPU from other agents. There is no initial coalition formation stage to hastily identify potential candidates and rank them. It directly negotiates with each agent in order of the succeeding agents until the needed CPU is satisfied. Thus, in some degree, it can avoid mutually requesting between two agents. Each agent determines the feasibility of giving agent A one part of CPU based on its own current allocated CPU (_currentCpuAlloc) and the current CPU usage (_currentCpuUsage). In the near future, the initial coalition formation stage is implemented according to the statistics information. The potential candidates will be got and ranked from agent A’s coalition formation history.
5. Details in the implementation
(1) In the method Agent_impl::run_impl, during the initialization phase, we can assign a fixed value to each agent’s _currentCPUAlloc whose sum is up to 66%.
(2) We will add a new method checkCPU in the class Agent_impl that will check the CPU shortage time by time.
(3) There are two Boolean variables: sendCpuRequest and cpuShortage. At the very beginning, sendCpuRequest = true and cpuShortage = false.
if (_cpuAlloc < _currentCPUAlloc)
cpuShortage=true;
if (sendCpuRequest==true) and (cpuShortage==true) and (coalition==undecided) {
sendCpuRequest to its following agent;
/** For example, in the agent list 0, 1, 2, 3, the agent 0 will ask help from 1.
If agent 1 has not enough CPU for agent 0, agent 0 will ask help from 2,
and then 3. Accordingly, the agent 1 will ask help from agent 2, 3 then 0. */
if all agents can't satisfy agent 0
the coalition result for agent 0 is "Failure" and the checkCPU stops;
else if agent 0 has not asked help from all other agents
it will send CPU request to next agent and set sendRequest =false;
}
else do nothing;
(4) In the method Agent_impl::parseAndRepsond, add three message type: cpuRequest, cpuResponse and cpuAcknowledge. At the same time, add three methods: handleCpuRequest, handleCpuResponse and handleCpuAcknowledge.
If the message is of type cpuRequest, call the method handleCpuRequest to do:
If agent B gets a cpuRequest message from agent A
Agent B checks to see if its own _currentCpuAlloc >_currentCpuUsage;
If (_currentCPUAlloc >_currentCPUUsage) and
(_currentCPUAlloc - _currentCPUUsage - _cpuMaxConsumed >
_cpuRequested)
Agent B sends a cpuResponse message to A based on FIFS with the given
up CPU amount
Else
Agent B returns a cpuResponse message to agent A with CPU amount 0
If the message is of type cpuResponse, call the method handleCpuResponse to do:
If agent A gets a cpuResponse message from agent B
Agent A parses the message to see if the CPU amount is 0;
If yes
set sendRequest to true;
else
check the current total CPU to see if the CPU amount can satisfy itself
If yes
Set coalition to Success and set cpuShortage to false;
Send cpuAcknowledge message to each agent who is involved in
Negotiation;
Agent A will add cpuRequest amount to its _currentCPUAlloc;
Else
If all the other agents have responded
Finish coalition formation process, unsatisfiable;
Else
Wait for next response from the next agent;
If the message is of type cpuAcknowledge, call the method handleCpuAcknowledge to do:
If agent B gets a cpuAcknowledge message from agent A
Subtract CPU amount from _currentCpuAlloc;
2005FTARTAWKSP016 ECONOMY REPORT CHILE SUBMITTED BY MS KAREEN
8 PREPARING STATISTICAL REPORTS ON PSYCHOTROPIC SUBSTANCES
ACC 4152 IMPAIRMENT ASSESSMENT (ACCREDITED EMPLOYER) REPORT PLEASE
Tags: coalition formation, finish coalition, coalition, report, formation