Random Access Machine ModelInmemory data structure:- Linked list; arrary, queue; tree; graphIn memory algorithms:- Sorting: O(nlog n), Scanning: O(n), Search: O(log n)
Random Access Machine Model • In memory data structure: − Linked list; arrary; queue; tree; graph • In memory algorithms: − Sorting: O(nlog n)，Scanning: O(n), Search: O(log n)
Hierarchical MemoryRLLAM.Modern machines have complicated memory hierarchy- Levels get larger and slower further away from CPU-Data moved between levels using large blocks
Hierarchical Memory • Modern machines have complicated memory hierarchy − Levels get larger and slower further away from CPU − Data moved between levels using large blocks L L R A M
Slow IODisk access is 106 times slower than main memory accessread/writearmtrack"ThedifferenceinspeedbetweenmodernCPU anddisktechnologiesis analogoustothedifferencein speedin sharpeningapencilusinga sharpeneron4835 1915 5748 4125one'sdeskorbytakinganairplanetotheother sideofthemagnetic surfaceworldandusingasharpeneronsomeone else 's desk."(D. Comer)- Disk systems try to amortize large access time transferring largecontiguous blocks of data (8-16Kbytes)- Important to store/access data to take advantage of blocks (locality)
Slow I/O − Disk systems try to amortize large access time transferring large contiguous blocks of data (8-16Kbytes) − Important to store/access data to take advantage of blocks (locality) • Disk access is 106 times slower than main memory access track magnetic surface read/write arm “The difference in speed between modern CPU and disk technologies is analogous to the difference in speed in sharpening a pencil using a sharpener on one’s desk or by taking an airplane to the other side of the world and using a sharpener on someone else’s desk.” (D. Comer) 4835 1915 5748 4125
Scalability Problems·Mostprograms developedinRAM-model-Run on large datasets becauseOs moves blocks as needed? Moderns OS utilizes sophisticated paging and prefetching strategies-But if program makes scattered accesses evengood OS cannottake advantage of block accessa uun\Scalability problems!data size
Scalability Problems • Most programs developed in RAM-model − Run on large datasets because OS moves blocks as needed • Moderns OS utilizes sophisticated paging and prefetching strategies − But if program makes scattered accesses even good OS cannot take advantage of block access Scalability problems! data size running time