From OpenCog

Scheduling: Allocating Attention Among MindAgents

We now discuss in detail how processor time is allocated in OCP, within a single Unit.

At the highest level, processors are allocated to OpenCogPrime:UnitGroups and OpenCogPrime:Units.

One level down from there, processor time is given within each OpenCogPrime:Lobe (remember, multiple OpenCogPrime:Lobes comprise a OpenCogPrime:Unit)

  • to CIM-Dynamics, implemented within each Lobe as MindAgents, which then select Atoms and act on them
  • to OpenCogPrime:Tasks, spawned by MindAgents and sometimes by other core processes

So, at the OpenCogPrime:Lobe level, attention allocation in OCP has two aspects: how MindAgents and Tasks receive attention from OCP, and how Atoms receive attention from different CIM-Dynamics. The topic of this page is the former. The latter is dealt with elsewhere, in two ways:

The Attention Allocation subsystem is also pertinent to MindAgent scheduling, because it discusses dynamics that update ShortTermImportance (STI) values associated with MindAgents, based on the usefulness of MindAgents for achieving system goals. In this page, we will not enter into such cognitive matters, but will merely discuss the mechanics by which these STI values are used to control processor allocation to MindAgents.

We have multiple kinds of CIM-Dynamics, which can be grouped in innumerable ways among different Units. Multiple instances of the same CIM-Dynamic can co-exist in the system, either in the same or in different Units. One can think of a CIM-Dynamic as a class in an object-oriented system, which can be instantiated multiple times, with different properties each time. (Each instantiation is a particular MindAgent running on a particular machine within a particular Unit.) This gives us several options, including:

  1. Allocate attention by the type of CIM-Dynamic, and then sub-allocate attention for each instance.
  2. Allocate attention directly to each CIM-Dynamic instance, in a single step.

While the former option would give us finer-grained control of the system, we feel that the latter is both more cognitively natural and more efficient. Therefore, we have chosen to attach an AttentionValue object to each CIM-Dynamic, and use it to schedule processor time. Each CIM-Dynamic then has an STI value (along with possibly other AttentionValue components), which is meaningful in the context of its hosting Unit.

An Example Scheduler Design

Each Lobe within a Unit has a Scheduler, which allocates slices of processor time to the MindAgents hosted in that Unit. At any given time, the Scheduler is enacted when a processor becomes available, and it has to decide which MindAgent will become active next. The simplistic approach is to keep a pool of inactive MindAgents, and select one from the pool, with a probability proportional to its normalized STI. However, things aren't that simple, and this heuristic fails to take into consideration a number of factors:

  • Attention needs to be given proportionally to the importance of each CIM-Dynamic. The importance of the CIM-Dynamic is altered dynamically by the Unit and by other CIM-Dynamic (a topic to be discussed later on, under the general rubric of economic attention allocation)
  • Starvation has to be prevented — even the least important CIM-Dynamic needs to receive some attention from the system.
  • In SMP machines, multiple CIM-Dynamics will be active at any given time. Some dynamics will not behave properly if executed at the same time as other dynamics.

This suggests that a moderately complex scheduling algorithm is required.

In this section we describe one such algorithm, which was implemented in the NCE. It is not adequate for long-term OCP usage and the current (July 2008) OCP code contains something even simpler that is also not adequate for long-term usage. This page will be updated with more details regarding scheduler designs in the hopefully near future. Note that scheduling is a fairly mature area of computer science due to its importance in the design of operating systems for various types of devices, so this is not an area where new ideas need to be invented for OCP; rather, designs need to be crafted meeting OCP's specific requirements based on state-of-the-art knowledge and experience.

In the example scheduler design, there are two important inputs:

  • An exclusion list for each MindAgent, listing the MindAgents that it has incompatibilities which. Incompatible MindAgents can't be run concurrently.
  • The STI associated with each MindAgent.

In the current NCE implementation, the Scheduler maps the MindAgent importances to a set of priority queues Q, and each queue is run a number of times per cycle. The number of queues is a parameter, and the function that maps a queue's priority level to the number of executions is:

executions-per-cycle = priority-level

where i is usually 1. In possession of the number of times each MindAgent should be executed, the Scheduler builds a binary matrix, in which each column corresponds to one MindAgent, and each row corresponds to one step in the cycle. Two MindAgents are set to true in the same row only if they can be run concurrently.

This matrix drives scheduling for that cycle. It is compacted through merging of rows with compatible restrictions (the optimal solution for this minimization problem is very expensive to find, but simple heuristics work well), to reduce overhead. Threads are assigned to the MindAgents and activated/put to sleep as the Scheduler goes through the steps.

When the importance of a CIM-Dynamic or other MindAgent changes, one just has to add/remove a few true flags in the matrix, which is a cheap operation. When MindAgents are added or removed, one has to rebuild the whole matrix, which is more expensive, but still doable, as it's not a very frequent operation inside a Unit.

Finally, Task execution is currently handled via allocating a certain fixed percentage of processor time, each cycle, to executing the top Tasks on the queue. Adaptation of this percentage may be valuable in the long term but was not yet implemented in NCE.