DOC PREVIEW
Duke CPS 100E - Memory Model

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CompSci 100E39.1Memory Modelÿ For this course: Assume Uniform Access Timeþ All elements in an array accessible with same time costþ Reality is somewhat differentÿ Memory Hierarchy (in order of decreasing speed)þ Registersþ On (cpu) chip cache memoryþ Off chip cache memoryþ Main memoryþ Virtual memory (automatically managed use of disk)þ Explicit disk I/Oþ CD-ROM, network file system, tapes, other slow devicesÿ All but last two managed by systemþ Need to be aware, but can do little to manipulate others directlyþ Promote locality?CompSci 100E39.2Cost of Disk I/Oÿ Disk access 10,000 to 100,000 times slower thanmemory accessþ Do almost anything (almost!) in terms of computation toavoid an extra disk accessþ Performance penalty is hugeÿ B-Trees designed to be used with disk storageþ Typically used with database applicationsþ Many different variationsþ Will present basic ideas hereÿ Want broad, not deep treesþ Even log N disk accesses can be too manyCompSci 100E39.3External Methodsÿ Disk use requires special considerationþ Timing Considerations (already mentioned)þ Writing pointers to disk?þ What do values mean when read in at a differenttime/different machine?ÿ General Properties of B-Treesþ All Leaves Have Same Depthþ Degree of Node >2þ (maybe hundreds or thousands)ÿ Not a Binary Tree, but is a Search Treeþ There are many implementations...þ Will use examples with artificially small numbers toillustrateCompSci 100E39.4Rules of B-Treesÿ Rules1. Every node (except root) has at least MINIMUM entries2. The MAXIMUM number of node entries is 2*MINIMUM3. The entries of each B-tree are stored, sorted4. The number of sub-trees below a non-leaf node is onegreater than the number of node entries5. For non leaves:þ Entry at index k is greater than all entries in sub-tree kþ Entry at index k is less than all entries in sub-tree k+16. Every leaf in a B-tree has the same depthCompSci 100E39.5ExampleExample B Tree (MAX = 2)[6]******[2 4] [9]*** ***** * **** * *[1] [3] [5] [7 8] [10]CompSci 100E39.6Search in B-Treeÿ Every Child is Also the Root of a Smaller B-Treeÿ Possible internal node implementationclass BTNode { //ignoring ref on disk issueint myDataCount;int myChildCount;KeyType[] myKeys[MAX+1];BTNode[] myChild[MAX+2]}ÿ Search pseudo-code:boolean isInBTree(BTNode t, KeyType key);1. Search through t.myKeys until t.myKeys[k] >= key2. If t.myData[k] == key, return true3. If t.isLeaf() return false4. return isInBtree(t.myChild[k])CompSci 100E39.7Find ExampleExample Find i n B-Tree (MAX = 2)Finding 10[6 17]** *** *** *** *** *[4] [12] [19 22]** ** ***** * * **********[2 3] [5] [10] [16] [18] [20] [25]CompSci 100E39.8B-Tree Insertionÿ Insertion Gets a Little Messyþ Insertion may cause rule violationþ “Loose” Insertion (leave extra space) (+1)þ Fixing Excess Entriesÿ Insert Fixþ Splitþ Move up middleþ Height gained only at rootÿ Look at some examplesCompSci 100E39.9Insertion Fixÿ (MAX = 4) Fixing Child with Excess Entry: Split[9 28] BEFORE******** *** *[3 4] [13 16 19 22 25] [33 40]*** * **** * ****** * * * * * * ****** * * * * * * * * *[2 3][4 5][7 8][11 12][14 15][17 18][20 21][23 24][26 27][31 32][34 35][50 51][9 19 28] AFTER*** **** **** **** *[3 4] [13 16] [22 25] [33 40]*** * ** ** * ****** * ** ** * ****** * * * * * * * * *[2 3][4 5][7 8][11 12][14 15][17 18][20 21][23 24][26 27][31 32][34 35][50 51]CompSci 100E39.10Insertion Fix (MAX= 2) Another Fix[6 17] BEFORE***** *** *[4] [12] [18 19 22][] STEP 2**[6 17 19]** * *** * *** **[4] [12] [18] [22][6 17 19] STEP 1************[4] [12] [18] [22][17] AFTER****[6] [19]** **********[4] [12] [18] [22]CompSci 100E39.11B-Tree Removalÿ Removeþ Loose Removeþ If rules violated: Fixo Borrow (rotation)o Joinÿ Examples left to the “reader”CompSci 100E39.12B-Treesÿ Many variationsþ Leaf node often different from internal nodeþ Only leaf nodes carry all data (internal nodes: keys only)þ These examples didn’t distinguish keys from dataþ Design to have nodes fit disk blocko (hardware dependent)ÿ The Big Pictureþ Details can be worked out to match your needsþ Can do a lot of computation to avoid a disk


View Full Document

Duke CPS 100E - Memory Model

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Memory Model
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Memory Model and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Memory Model 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?