Browse Prior Art Database

METHOD FOR SERIALIZING ORDER SO AS TO MINIMIZE COLLISION IMPACTS

IP.com Disclosure Number: IPCOM000014047D
Original Publication Date: 1999-Oct-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 3 page(s) / 42K

Publishing Venue

IBM

Related People

KF SMITH: AUTHOR

Abstract

At times it is advantageous to order a group of events relative to each other so as to enhance their combined inter-relationships. For example, consider the case where I/O performance is to be measured. Suppose that a total of four different files are to be included as a part of two different measurements, each involving a different two of the four files. Further suppose that two of the files are on the same disk drive. In such a situation the I/O performance results will not be maximized should we measure the two files on the same disk drive at the same time and then subsequently measure the other two files. We would do better to measure each of the two files individually, albeit paired with one of the other four files in the measurement group. This problem becomes more acute when we consider a variety of overlapping physical constraints, such as internal pathing constraints, shared adapter cards, control units as well as a variety of other possible shared resources. Of course this problem is not limited to measuring I/O performance results, however it does serve our purposes here of providing an illustrative example. The purpose of this paper is to describe an algorithm such that overlapping constraints can be accounted for and thus avoided (or sought after (by reversing the 'goodness' measure)) thereby providing a serialization order that is near-optimal for the problem domain.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

METHOD FOR SERIALIZING ORDER SO AS TO MINIMIZE COLLISION IMPACTS

   At times it is advantageous to order a group of events relative to each other so as to enhance their combined inter-relationships.

For example, consider the case where I/O performance is to be measured. Suppose that a total of four different files are to be included as a part of two different measurements, each involving a different two of the four files. Further suppose that two of the files are on the same disk drive. In such a situation the I/O performance results will not be maximized should we measure the two files on the same disk drive at the same time and then subsequently measure the other two files. We would do better to measure each of the two files individually, albeit paired with one of the other four files in the measurement group.

This problem becomes more acute when we consider a variety of overlapping physical constraints, such as internal pathing constraints, shared adapter cards, control units as well as a variety of other possible shared resources. Of course this problem is not limited to measuring I/O performance results, however it does serve our purposes here of providing an illustrative example.

The purpose of this paper is to describe an algorithm such that overlapping constraints can be accounted for and thus avoided (or sought after (by reversing the 'goodness' measure)) thereby providing a serialization order that is near-optimal for the problem domain.

The Serialization Process

Overview

The serialization process involves two major steps:

Assign a cannonical numbering to the resources at each level of possible overlap based upon their uniqueness at that level. Assign 'goodness' measures to the remainder of the resources based upon overlap with all previously assigned resources, one at a time, iteratively, until all resources have been assigned, such that the most favorable 'goodness'
measure is selected in each instance.

The resulting assigment order is the desired serialization order.

The 'goodness' measure can of course be any appropriate quantification, however for our purposes it is sufficient to say that the possibly-overlapping resource groupings are each assumed to be of equal importance within each group, but of absolute importance relative to other groupings. In other words, some resource groupings are much more important to avoid overlapping use of than other groupings, and that the resource groupings are specified in the order of their importance. In the algorithm below the order of importance will proceed from left to right, the left-most grouping being of the greatest importance to avoid overlapping collisions with.

Methodology

Terminology

Variable Name Description

R[i,j] Resource name for item #i in group #j

1

Page 2 of 3

K...