Browse Prior Art Database

Time bound of Nonvolatile Bitmap Initialization

IP.com Disclosure Number: IPCOM000031028D
Original Publication Date: 2004-Sep-07
Included in the Prior Art Database: 2004-Sep-07
Document File: 2 page(s) / 44K

Publishing Venue

IBM

Abstract

Presented herein is a method for breaking the task of setting up bitmaps into sub-tasks and deferring the sub-tasks such that each sub-task is performed when the relevant bitmap is needed, not at the time the bitmap is logically set. At the time the bitmap is logically set, the time required is constant, independent of the size of the bitmap.

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

Page 1 of 2

Time bound of Nonvolatile Bitmap Initialization

Nonvolatile bitmaps are a common data structure used in many storage solutions as well as other systems. In many cases the size of the bitmaps is a function of the size of the configuration. Often, a nonvolatile bitmap is stored on several tracks on a block storage device, the number of tracks depending on the size of the bitmap. Access to these tracks is associated with long access time. Hardening a change to the nonvolatile storage may also be associated with a long delay.

    An initialization of a bitmap requires accessing the nonvolatile memory on which it resides, updating the values on the bitmap, and possibly hardening the changes. It is desirable to give a reasonable bound to the initialization time. All of these operations take time, which is a function of the size of the bitmap.

    There are two existing solutions to the problem: One solution is to set a heuristic time bound on the bitmap setup operation such that, in practice, no bitmap setup will exceed it. This heuristic time bound may be exceeded under extreme conditions. The other solution is to initialize several portions of the bitmap in parallel. This solution may significantly reduce the initialization time, but the amount of parallelism that can be achieved is restricted due to hardware limitation. As a result, the initialization time still remains dependent on the size of the configuration. With both solutions the time it takes for the operation to complete is a function of the size of the configuration, which is undesirable.

    Presented herein is a method for breaking the task of setting up the bitmaps into sub-tasks and deferring the sub-tasks such that each sub-task is performed when the relevant bitmap is needed, not at the time the bitmap is logically set. At the time the bitmap is logically set, the time required is constant, independent of the size of the bitmap.

    Each sub-task incurs part of the setup time of the whole bitmap, but the time incurred by each sub-task is independent of the size of the overall configuration.

The proposed method has several advantages:

A bound on the setup time for the bitmap can be defined independent of the size


1.


2.


3.


4.

of the configuration.

The initial time required to setup is very short.

It may be more efficient, since the sub-operations can be performed at a time

when the incurred overhead is minimal, for example when access to the metadata track is required for another reason.

In cases where parts of the bitmap are never used, the relevant sub-operations

with their overhead can be avoided altogether.

During the logical setup of the bitmap the bitmap is assigned a generation number. This is the Logical Setup Generation Number. This generation number is later used to identify which portions of the bitmap were initialized and which were not.

    The bitmap is divided into portions of a fixed size. Each portion has two sub-tasks associated with it: initializing the values in the bit...