Allocating storage for aligned data

Details Allocating storage for aligned data Allocating storage for aligned data

2001-03-23

2003-01-14

Yoo, Do Hyun (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Memory configuring

C711S171000, C707S793000, C707S793000

Reexamination Certificate

active

06507901

ABSTRACT:

BACKGROUND
As computer software developers develop software for 64-bit processors, data alignment in data storage, such as a disk, will become extremely important. “Alignment” in the data storage context refers to limitations placed on the address of a data object in the data storage. For example, a common “alignment requirement” is that the address of a data object must be a multiple of a power of 2, i.e. 2
N
, which means that the least significant N digits of the address must be zero.
Alignment is important for functional reasons because an unaligned data access may cause a bus error resulting in a system crash. Alignment is also important for performance reasons because unaligned data access, which can be handled with hardware or software alignment correction tools, will likely become more expensive as processor speeds continue to increase.
Data stored in a data storage is typically heterogeneous, in the sense that it consists of elements with varying alignment requirements. It is easy to optimize the storage space allocated for the data, in the absence of alignment requirements, by simply packing the elements one after another. However, imposing alignment requirements on the data elements may force the introduction of padding to fill holes in storage caused by the alignment requirements. This padding may increase the amount of storage required to store the data elements. The amount of storage required to store the data elements may depend on the order in which the data elements are arranged in storage. This is because the padding necessary to accommodate the data alignment requirements may be different depending on the order that the data elements are stored.
SUMMARY
In general, in one aspect, the invention features a method for allocating storage for a header and one or more data elements in a data storage facility. The data storage facility is divided into words. Each word includes one or more incidents of one or more types of alignment boundaries. Each incident of a type of alignment boundary falls on a multiple of a base amount of units from the beginning of the word. The base amount is unique for each type of alignment boundary. Each data element is required to satisfy an alignment requirement, which is the size of alignment boundary with which it is required to align. Each data element has a length that is a multiple of its alignment requirement. The method includes computing a hole size, B, that is a portion of a word that would be unallocated if storage were allocated to the header and to the data elements in a preferred order. The method further includes finding a subset of data elements S={F
i1
, F
i2
, . . . , F
in
} that satisfy the following equation:
(SizeMod
N
(
F
i1
)+SizeMod
N
(
F
i2
)+ . . . +SizeMod
N
(
F
in
))mod
N=B
where SizeModN(F) is the size of F modulo N, and N is the largest alignment requirement associated with any data element. The method further includes allocating storage to data elements in S first and allocating storage to the remaining data elements in the preferred order.
Implementations of the invention may include one or more of the following. Finding the subset of data elements S may include accessing a lookup table using N and B as indexes to retrieve a first set of one or more modulo values M
1,1 . . . R
and a frequency F
1,1 . . . R
for each modulo value. Finding the subset of data elements S may further include searching for a subset T={A
i1
, A
i2
, . . . , A
in
} of data elements, such that for every p from 1 to R there is a set of F
1,p
data elements such that the size of those data elements modulo N is M
1,p
, and setting S=T. Finding the subset of data elements S may further include, if the search for a subset T of data elements fails using the first set of one or more modulo values M
1,1 . . . R
and the frequency F
1,1 . . . R
for each modulo value, accessing the lookup table again using N and B as indexes to retrieve a second set of one or more modulo values M
2,1 . . . R
and a frequency F
2,1 . . . R
for each modulo value and searching for a subset T using M
2,1 . . . R
and a frequency F
2,1 . . . R
. The method may then set S=T. Finding the subset of data elements S may further include, if the search for a subset T of data elements fails, setting B=B−1 and repeating the search.
In general, in another aspect, the invention features a lookup table useful in allocating storage for a header and one or more data elements in a data storage facility. The data storage facility is divided into words. Each word includes one or more incidents of one or more types of alignment boundaries. Each incident of a type of alignment boundary falls on a multiple of a base amount of units from the beginning of the word. The base amount is unique for each type of alignment boundary. Each data element is required to satisfy an alignment requirement, which is the size of alignment boundary with which it is required to align. Each data element has a length that is a multiple of its alignment requirement. The lookup table includes a plurality of solution data objects, each of which includes one or more data element modulus objects D
1 . . . n
, each data item modulus object containing a data item size modulo the largest alignment requirement associated with any data element. Each of the plurality of solution data objects further includes a frequency object F
1 . . . n
for each respective data item modulus object. Each frequency object contains the number of respective data elements required, in combination with the other data elements identified by the data element modulus objects to satisfy the following equation:
(
F
1
·D
1
+F
2
·D
2
+ . . . +F
n
·D
n
)mod
N=B
where B is the size of a portion of a word that would be unallocated if storage were allocated to the header and to the data elements in a preferred order, and N is the largest alignment requirement associated with a data element.
Implementations of the invention may include one or more of the following. Each solution data object may include a count data object that contains the number of data element modulus objects in the respective solution data object. The solution data objects may be grouped into hole size data objects, where each hole size object is associated with a selected value of B. The hole size objects may be grouped into alignment data objects, where each alignment object is associated with a selected largest alignment requirement.
In general, in another aspect, the invention features a method for building a lookup table for allocating storage for a header and one or more data elements in a data storage facility. The data storage facility is divided into words. Each word includes one or more incidents of one or more types of alignment boundaries. Each incident of a type of alignment boundary falls on a multiple of a base amount of units from the beginning of the word. The base amount is unique for each type of alignment boundary. Each data element is required to satisfy an alignment requirement, which is the size of alignment boundary with which it is required to align. Each data element has a length that is a multiple of its alignment requirement. The method includes for s from 1 to t, performing the following
for selected s-tuples (x
1
, x
2
, . . . x
s
) and for B ranging from 1 to p find the smallest frequencies (f
1
, f
2
, . . . f
s
) such that
(
x
1
·f
1
+x
2
·f
2
+ . . . +x
s
·f
s
)mod
N=B.
where N is the largest alignment requirement associated with a data element, t is an upper limit on the number of distinct elements in a valid solution, and p is N−1.
Implementations of the invention may include one or more of the following. t may be 3 and p may be 7. The method may further include storing the s-tuples and respective frequencies in the lookup table indexed by B. The sum of two or more elements of each selected s-tuple may not equal 2
t
or a multiple of 2
t
. The selected 3-tuples when t is 3 may include: (1,2,3), (1,2,4)

Affiliated with

Also associated with

Rating

Allocating storage for aligned data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Allocating storage for aligned data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Allocating storage for aligned data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3030452