A Few Examples of the Need for Open Implementations

Here are a few examples of domains in which there are significant mapping dilemmas, i.e. important choices to be made among several ways of implementing a higher-level functionality in terms of lower level ones; and where the dilemmas result in mapping conflicts, i.e. where no one choice can give all clients good performance.

• Virtual Memory - In the case of virtual memory, the basic functionality is particularly simple: a bunch of memory addresses that can be read or written. There are mapping dilemmas having to do with how to map virtual addresses to pages, and how to map those pages to physical memory at any given time. (This second concern breaks down into individual issues of page replacement policy, page ahead policy etc.)

  A classic conflict happens when a client, such as a database system, does a ``scan'' of one portion of its memory, while doing random access to another portion. A virtual memory implementation based on an LRU will perform poorly in this case.

• Parallel Programming Languages - The basic functionality is to provide a natural way of expressing a computation to be executed in parallel. There are three principle mapping dilemmas: how to distribute the computation across the physical processors, how to distribute the data and how to perform synchronization. A common source of mapping conflicts is in the layout of matrices. As a simple example consider that if the compiler distributes the ith rows of two matrices A and B to the same processor, then matrix addition will require no communications overhead, but matrix multiplication will be communication intensive.

• Communication - One basic functionality is a stream of data. Some of the mapping dilemmas have to do with message buffering, retry policies, synchronization and ordering constraints.

  Mapping conflicts arise because different applications require very different qualities of service. For example, an application sending payroll information wants all the data to arrive, even if it delays the overall transmission. On the other hand, for an application sending JPEG data, some packets are less significant, and it isn't worth their being retransmitted if that would delay processing on the receiver.

Return to the Open Implementation Site Guide Return to the Open Implementation Home Page