InnovationQ will be updated on Sunday, May 20, from 10am - noon ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Technique to Enable Addressability of Interlaced Operands of a Multiprocessor Random Test Streams

IP.com Disclosure Number: IPCOM000020018D
Original Publication Date: 2003-Oct-17
Included in the Prior Art Database: 2003-Oct-17
Document File: 3 page(s) / 45K

Publishing Venue



This disclosure introduces a technique to alleviate operand addressability for random test instruction streams intended to maximize cache contention among different processors. To verify whether memory coherency is maintained it is desirable to use random test instruction streams with interlaced operands. Operand interlacing is meant to generate different test instruction streams where: - in storage, a given pair of operands belonging to the same instruction stream are separated by a number of operands of different instruction streams and - the outcome of the execution of each instruction stream appears as if the store-type operands between these different instruction streams do not intersect (see Figure 1). During the stream building, operands are allocated in a round-robin fashion such that a task is interrupted at each memory allocation to give other tasks chances for operand allocations. The operand allocation mechanism repeatedly polls tasks and, each time, collects one instruction from each task with allocation requirement. As the number of tasks participating in the test increases, the distance between two given operands of the same instruction may become larger. Furthermore, if operands can be selected from a number of noncontiguous memory locations, a given operand may not be accessable to a task due base register scarcity. Therefore, a task may face addressability problem since, based on the current state of the stream such as the values of the task's base and/or index registers, the task may not reach one of its operands.

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 52% of the total text.

Page 1 of 3

  A Technique to Enable Addressability of Interlaced Operands of a Multiprocessor Random Test Streams

  This disclosure eliminates addressability problems by providing an operand allocation algorithm, when operands are allocated from contiguous memory locations, and a dynamic register management algorithm when operands are allocated from oncontiguous memory locations. These algorithms enhance the scalability of operand interlacing and are capable of supporting systems with any number of processors.

Contiguous Memory Locations: depending upon architecture, operand size, number of tasks, etc., the distance between two allocations for a single instruction may become large such that addressing the second operand is not possible given the current state of the instruction stream. (For simplicity, let us assume that each base/index register of the task is being used to address at least one operand.) When the first operand is allocated, any valid address for the second operand is bounded by the values in the base/index registers of the task. Since the values of the base/index registers cannot be altered after they are used to address operands, the second operand location must be within the range of at least a one base register value, or a combination of a base and an index registers values (i.e., can be reached by changing the only the offset field). Otherwise, the instruction will not be able to reach the operand. A task with allocation requirement is admitted to participate in the allocation process if the task is determined that it does not cause addressability problem for another task. In this case the allocation for the task that is causing an addressability problem is deferred. Denying task(s) to join the allocation process does not prevent other tasks to join the allocation process as long as these tasks do not create an addressability problem. The aim is to preserve the round-robin scheduling as much as possible. Although a given task may be denied to participate in the allocation process a number of times, none of the tasks may experience starvation as will be explained shortly.

Among the number of tasks participating in the allocation process, the task with the least reachability and whose current instruction has more than one operand is selected as the admission controller. Initially there is no admission controller and any task can participate in the allocation process. Admission controller is selected when an operand is allocated for an instruction I with more than one operand. Before a request of a task to join the allocation process is honored, this method checks if the task may cause addressability problem to the current addmission controller. If the address of the most recently allocated operand plus the total number of bytes to be allocated for the requesting task exceeds the maximum location addressable by the admission controller, the task is denied to participate in the allocation process. Once the admission...