Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-02-23
2001-11-27
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06324540
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to methods of and apparatus for partitioning an array of items, and more particularly to partitioning an array of n items into p subarrays so that a maximum weight of the array elements within any subarray is minimized.
2. Background of Related Art
Array partitioning problems arise in a number of load balancing, scheduling, data layout, video compression and image processing settings. Although the present invention relates generally to the partitioning of multiple dimension arrays, for simplicity of description partitioning will be described herein with respect to two dimensions only, with the understanding of the applicability to arrays of higher dimensions.
The problem of partitioning a set of items into roughly equal weight subsets is a fundamental one. Consider partitioning an n×n array of items into rows and columns having a number p of intervals there between in both dimensions. The p intervals in both dimensions can be understood as forming blocks of array elements. The present invention relates to and improves upon methods and apparatus for determining those partitions p which minimize a maximum weight given to the array elements in each of the resulting blocks. The ‘weight’ in this determination may be virtually any characteristic of the array elements particular to the application for which the invention is being utilized. For instance, for purposes of description only, the ‘weight’ of determined blocks in an n×n array will be defined as the sum of the array elements contained within the partitioned blocks.
The definition of the ‘weight’ associated with the partitioned blocks in an array, the type of partitions allowed, and the dimensions of the partitioned arrays depends upon the particular application at hand. Particular applications having n×n arrays with weighting based on the sum of the elements contained within the partitioned blocks include load balancing for parallel processing, data partitioning for parallel software, and compilers for high-performance parallel languages. Moreover, partitioning of n×n arrays is particularly applicable for use in the compression of the data required to represent a video signal. Some video compression techniques take advantage of the fact that typically only portions of a video image change from frame to frame based on the motion of an object. In this application, the present invention applies to the determination of motion estimation by matching partitioned blocks between frames of a video image. Here, it is typically desired that given a maximum desired weight &dgr; of any partitioned block, that the partitions be minimized such that the maximum weight of any partitioned block is at most the desired weight value &dgr;.
The present invention will generally be described with respect to the solution of two types of partitioning:
(a) Given a desired number of partitioned blocks B, partition a given array into at most B blocks having the weight of any partitioned block B minimized; and
(b) Given a desired maximum weight &dgr;, partition a given array into a minimum number of blocks B such that the weight of any block B in the partition is no greater than the desired maximum weight &dgr;.
There is a need for equipment such as that implementing parallel processing or image compression to partition multidimensional arrays of data with improved speed, efficiency and accuracy.
Conventional partitioning techniques are extended to two dimensions, e.g., when given a desired number of partitions p, the effort is to find the p×p partitions that minimize the maximum of the weight functions of the individual blocks. This is known as the “two dimensional p×p partition problem”. In a related situation extended into the two dimensional case, given a desired maximum value for the weight function &dgr;, find the minimum number of partitions p for which there exists p×p partitions forming blocks each having a weight function no greater than the desired maximum weight &dgr;. This is known generally as the “two dimensional &dgr;-weight partition problem.”
Consider AA to be an n×n array. The effort is to divide each column (e.g., AA[1, n]) into p intervals defined by horizontal dividers (h
0
=0)<h
1
≦h
2
≦. . . ≦h
p−1
≦(h
p
=n), and each row (e.g., AA[1,n]) into p other intervals defined by the vertical dividers (v
0
=0)<v
1
≦v
2
≦. . . ≦v
p−1
≦(v
p
=n). This partitioning defines p
2
blocks given by AA[h
i−1
+1 . . . h
i
, v
j−1
+1 . . . v
j
] for each i, j.
Two weight functions arise commonly in practice: the additive weight function:
F(A[i,j])=&Sgr;
k=i
k=j
A[k]
and the Hamming weight function H
c
for a given parameter c, relative to another array B of size n, given by:
H
c
(A[i,j])=min
−c≦k≦c
H(B[i+k,j+k],A[i,j])
where H(X,Y) gives the Hamming distance between two segments X and Y of identical length.
Using either of these or another weight function, the resultant maximum of the weight values is determined by:
maxi
i=1
i=p
f(A[d
i−1
+1 . . . d
i
])
Conventional weight functions for the partitioned blocks are the additive weight function F or the Hamming weight function H
c
.
The minimum of the maximum weights of the individual blocks in a partition (MAX norm) is given by:
max
i=1,j=1
i=p,j=p
f(AA[h
i−1
+1 . . . h
i
,&ngr;
j−1
+1 . . . &ngr;
j])
Given a desired number of partitions p, a practical example of a two dimensional p×p partition problem using an additive weight function is now given.
For data stored in two dimensional arrays, several high performance computing languages allow the user to specify a partitioning and distribution of data onto a logical set of processors. An example of such a scheme is what is known as the generalized block distribution in HPF (high performance Fortran), which is a two dimensional p×p partition problem using an additive weight function F.
The two dimensional p×p partition problem using a Hamming weight function is exhibited in motion-compensated video compression by block matching. Since successive frames of a video sequence are strongly correlated, frames can be compressed by reference to the preceding ones. This can be improved by first estimating portions of the current frame which correspond to moving objects and then transmitting motion vectors that indicate to the decoder where to look at the previous frame to predict the current one. The most popular method for estimating the motion vectors is called block matching as discussed in J. Jain and A. Jain, “Displacement Measurement and its Application in Interframe Coding”, IEEE Transactions on Communications, vol. 29, pp. 1799-1808 (1981), which is expressly incorporated herein by reference. This involves tiling the current frame with blocks and estimating the motion vectors for each block individually. The motion vector for a given block is usually obtained by minimizing, from among candidates v within a limited search area, some norm of the difference between the block and the previous frame at v. An example is the minimum Hamming distance between B and v within a window of width C around the position corresponding to B in the previous frame, for some parameter C. The main variation is in how the current frame is tiled. Some extant tilings use fixed-sized blocks as discussed in J. Jain and A. Jain, “Displacement Measurement and its Application in Interframe Coding”, IEEE Transactions on Communications, vol. 29, pp. 1799-1808 (1981), superblocks as discussed in B. Carpentieri and J. Storer, “A Split-Merge Parallel Block Matching Algorithm for Video Displacement Estimation”, Proc. Of IEEE Data Compression Conference, pp. 239-248 (1992), and quadtrees as discussed in D. Hoang, P. Long and J. Vitter, “Ex
Khanna Sanjeev
Muthukrishnan Shanmugavelayut
Black Thomas
Bollman William H.
Lucent Technologies - Inc.
Mills John G.
LandOfFree
Apparatus and method for efficiently partitioning a weighted... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for efficiently partitioning a weighted..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for efficiently partitioning a weighted... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2607049