Browse Prior Art Database

Last Recently Serviced Thread Interleaving

IP.com Disclosure Number: IPCOM000019515D
Publication Date: 2003-Sep-17
Document File: 2 page(s) / 41K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method that time interleaves multi-threading algorithms. Benefits include limiting the amount of queuing effect seen by multiple requestors to the same resource.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 53% of the total text.

Last Recently Serviced Thread Interleaving

Disclosed is a method that time interleaves multi-threading algorithms. Benefits include limiting the amount of queuing effect seen by multiple requestors to the same resource.

Background

Currently, there is one known interleaving scheme (i.e. a round robin scheme) where a pointer sweeps over the available threads and selects among those that are ready to be selected.

General Description

If there is a point where several requestors need to temporally share a resource, the disclosed method chooses which requestors among the ready ones should be selected. Using the round robin scheme, if N is the number of requestors accessing a resource, a requestor can have to wait N-1 cycles until it is selected, if there are N requestors, on average it can wait N/2 times.

For example, in the Figure’s left hand case, we have requestors A, B, C, D present at a temporally interleaved resource. Requestor B was selected last, and in the round robin scheme, the selection process moves on entry forward and selects entry C.

For the present disclosure, in the Figure’s right hand case, we have requestors X, Y, Z, W present and we have their last service time remembered. In this example requestor D was selected last and has the highest recorded time, 500. When a new selection is made, Request B was serviced the longest ago, at time 5, and becomes the new selection.

If all requestors are equally active there is no problem since on average the requestors will have to wait equally long. However, if one requestor is much less active than other requestor, it may have to wait longer for the few requests that it needs to perform. Also, the disclosed method is sensitive to beat patterns, where all requestors show up at the interleaving point at similar time intervals and must wait a long time. If a requestor is using a resource infrequently, it will only see a one cycle delay in getting through to the resource.

Note. A requestor that accesses a resource infrequently is more likely to be in latency mode and delays will have a large performance impact. A requestor that accesses a resource often is more likely to be in throughput mode and not be a...