Memory and Data Structures

60 pages
4 views

Please download to get full document.

View again

of 60
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Memory and Data Structures. Arrays Stacks Queues. Memory. This is the “RAM” in a system Labels and addresses point to pieces of memory holding: Words Bytes Strings Floats Memory is just a collection of bits
Transcript
Memory and Data StructuresArraysStacksQueuesMemory
  • This is the “RAM” in a system
  • Labels and addresses point to pieces of memory holding:
  • Words
  • Bytes
  • Strings
  • Floats
  • Memory is just a collection of bits
  • Can be used to represent integers, characters, or some arbitrary representation.
  • 2Memory
  • Instead: treat memory as a giant flat array of bytes
  • Compiler or Progammer decides what to make of it
  • Element numbering starts at 0
  • The element number is an address
  • In “C” memory is allocated by:
  • char m[size of array];3Storage of bytes
  • MIPS architecture is “byte addressable” meaning that all addresses are “byte” addresses.
  • This means the smallest unit of memory we can allocate is a byte.
  • Use ‘lb’ (load byte) to access this unit.
  • 4Storage of bytesExample .datamychar: .bytenewline: .byte ‘\n’ … .text … lb $t0, newline li $v0, 12 # getc syscall sb $v0, mychar beq $t0,$v0, found_newline …found_newline: …5Storage of bytesaddressesMemoryThe data is placed in memory like this at start up (assuming .data section starts at address 4).The mychar variable will change to the value of the character entered by the user once stored.newline variablemychar variable6Storage of Integers
  • Use 4 bytes beginning at an address that is multiple of 4.
  • So if stored at address 20, uses bytes 20, 21, 22, and 23.
  • Use ‘lw’ (load word) instead of ‘lb’ (load byte).
  • 7Storage of Integers .data n: .word 1 n2: .word -1 newline: .byte ‘\n’ str1: .asciiz “Enter a number ” .text main: la $a0, str1 li $v0, 4 # print string syscall li $v0, 5 # get integer syscall lw $t1, n add $t2, $v0, $t1 sw $t2, n28Storage of IntegersMemory 1 in 2SC-1 in 2SCNew line“Enter a number “addresses9Memory
  • And the program would become this eventually:
  • .text
  • main: li $a0, 49 # expects an address for a string
  • li $v0, 4 # code for put string
  • syscall
  • lw $t1, (40) # expects an address
  • add $t2, $t1, $t1 # expects “values”
  • sw $t2, (44) # expects an address
  • Real machine code has addresses for variables, not labels.
  • Later, we will show how to store instructions and get rid of branch labels. Then the .text segment will look similar to the .data segment.
  • 10Endian IssuesConsider this code: .datan: .word 0x61626364 #ASCII for ‘a’, ‘b’, ’c’, ’d’ .textmain: lb $a0, n li $v0, 11 # putc code syscallDo you think an ‘a’ or a ‘d’ is printed?11Endian IssuesAnswer: ‘a’ since MIPS is a big Big Endian architecture.memoryaddressesBut if we did:lw $s0, n310We would get this:As we would expect.12Endian Issues
  • Big Endian:
  • smallest address is most significant (biggest)
  • Little Endian:
  • smallest address is least significant (littlest)
  • So answer would be ‘d’
  • If we did a lw $s1, n
  • $s1 ← 0x61626364
  • memoryaddressesSame as with big endian13Word Address Bytes MSBLSB 0 3 2 1 0 4 7 6 5 4Word Address Bytes MSBLSB 0 0 1 2 3 4 4 5 6 7Endian IssuesBi-Endian:Selectable data formatLittle Endian – address LSB(VAX, Alpha, x86, PDP-11)Big Endian – address MSB(IBM 360390, Motorola 680x0, Sparc, MIPS)14Endian Issues
  • Programmable or bi-endian: on data only (why not instructions?)
  • i860 (Little-endian instructions)
  • PowerPC (Big-endian instructions)
  • In general:
  • When accessing values smaller than a word must alsoconsider alignment, sign extension, and effect on high bytes of register.
  • 15Arrays
  • Array implementation is very important
  • Most assembly languages have no concept of arrays
  • From an array, any other data structure we mightwant can be built
  • 16ArraysProperties of arrays:
  • Each element is the same size
  • Char = 1 byte
  • Integer = 1 word
  • Elements are stored contiguously
  • First element at the smallest memory address
  • In assembly language we must
  • Allocate correct amount of space for an array
  • Map array addresses to memory addresses
  • 17Arrays
  • MAL declarations of arrays within memory
  • To allocate a portion of memory (more than a singlevariable’s worth)
  • variablename: type initvalue:numelements
  • type is as before - .byte, .word, or .float
  • numelements is just that, numbering starts at 0 (as in C)
  • initvalue is a starting value given to each element of the array
  • 18Arrays
  • MAL declarations of arrays within memory
  • To allocate a portion of memory (more than a single variable’s worth)
  • variablename type init_value : num_elements
  • Type as before:
  • .byte .word or .float
  • Num_element: numbering starts at 0 (just like in “C”)
  • Init_value: the value of each element of the array
  • 19Arrays
  • New directive:
  • name: .space number_of_bytes
  • .space allocates space (in bytes) within memory without giving an initial value.
  • The type of the data within this space cannot be inferred.
  • 20Array ExamplesExamples:8 character elements, number 0 – 7, initialized to 0 arrayname: .byte 0:818 bytes of memory name: .space 185 integers initialized to 3 numbers: .word 3:521Element index0123456address25262728292A2BArray of BytesCalculating the address of an array element char myarray[7] /* C */ myarray: .byte 0:7 # MAL
  • If base address of myarray is 25
  • Byte address of myarray[4] = 25 + 4 = 29
  • Base address + distance from the first element
  • 22Addressing Byte Arrays
  • If we want the 3rd element
  • It is at index 2 since indexing starts at zero.
  • Thus myarray[2] is the at the address of array + 2.
  • If the 1st element is [0] and is at address 25, then the address of the 3rd element is myarray[2] = 25 + 2
  • 0123456indexaddress252627282930313rd element23Addressing Byte Arrays
  • How do you get the address of myarray?
  • Use the “load address” instruction, “la”
  • Keep clear the difference between an address and the contents of an address.
  • 24Addressing Byte Arrays
  • To get address of myarray[4] in MAL, write the code…
  • la $t0, myarrayadd $t1, $t0, 4
  • If we wanted to decrement element number 5 by 1…
  • lb $t4, ($t1) # ALT: lb $t4, 4($t1)
  • sub $t4, $t4, 1
  • sb $t4, ($t1)
  • 25Array of IntegersAn integer is 32-bits (word) and contains 4 bytesC++: int myarray[6];MAL: myarray: .word 0:6 Or myarray: .space 24 26index012345address8084888C9094Array of IntegersSo to find the address of myarray[x] we must find:
  • Where the array starts (base address)
  • Size of an element in bytes
  • Thus byte address of myarray[x] = base + size(x)
  • So the byte address of myarray[3] = 80+4(3) = 8C27lw vs. lbThe type of lb is ‘byte’ and of lw is ‘word’Use lb to manipulate bytesUse lw to manipulate words28lw vs. lbThe index of both lb and lw is a byte address.lba #address byte in memory location M[a]#The following indexes base[$t1]base: .byte 0:n .text la $t0, base add $t2, $t0, $t1 lb $t3, 0($t2)lw$t1, a # addresses the 4 bytes starting at M[a]Both lw and lb should always be used with a base address and allocated space.292-Dimensional Arrays
  • 2-Dimensional arrays are more complicated in assembly
  • Memory is a 1-D array
  • Must map 2-D array to 1-D array
  • Arrays have rows and columns
  • r x c array
  • r=rows
  • c=columns
  • 300,00,01,00,12,01,03,01,10,12,01,12,12,13,03,13,12-Dimensional ArraysTwo sensible ways to map 2-D to 1-DColumn major form:(columns are all together)Row major form:(rows are all together)4x2 example31More Array Examples: 3x5322-Dimensional Arrays
  • How do you calculate addresses in a 2-D array?
  • Row Major:
  • Column Major:
  • Base Address + element size(#columns x Ri + Ci)Base Address + element size(#rows x Ci + Ri)332-Dimensional Arrays
  • Summary of 2D arrays
  • Row/Column major (storage order)
  • Base address
  • Size of elements
  • Dimensions of the array
  • How about 3-D arrays?
  • 34Bounds Checking
  • Many HLL’s have bounds checking (not C!!!)
  • Assembly languages have no implied bounds checking
  • Your program is in total control of memory
  • With a 5 x 3 array, what does the following address?
  • array: .word 0:100
  • .text
  • la $t1, array
  • add $t1, $t1, 15
  • lw $t0, ($t1)
  • Bounds checking is often a good idea!!
  • Most C development environments include optional bounds checking.
  • 35Stacks
  • A data structure that stores data in the reverse orderthat it is used.
  • The data is not known until run time.
  • The classic analogy is a stack of dishes
  • You can put single plates on the stack
  • You can take plates off the stack
  • Last in, First out (LIFO)
  • 36Stacks
  • Data is added or “pushed” onto the stack.
  • Data is removed or “popped” off the stack.
  • 3rd on2nd on1st on37Stacks
  • Printing out a positive integer, character by character
  • Push LSB to MSB
  • Pop MSB to LSB (LIFO)
  • integer = 1024
  • if integer == 0 then
  • push ‘0’
  • else
  • while integer != 0
  • digit  integer mod base
  • char  digit + 48
  • push char onto stack
  • integer  integer div base
  • while stack is not empty
  • pop char
  • print char
  • 38Implementation of a StackOne implementation of a stack out of an array.
  • Index the top of stack (tos), with a stack pointer (sp).
  • initial state, sp points at top of stack
  • SP is a variable that contains the address of the emptylocation at the top of the stack (when empty).
  • 39Stack Implementation
  • In MAL:
  • stack: .word 0:50
  • stackend: .word stack+4x50
  • Or
  • stack: .space 200
  • Labels can be used as initial values
  • The address (label) of the stack gets put into the variable
  • 40Stack Implementation
  • Pushing and popping code
  • la $s0, stack #initialization of stack ptr
  • PUSH
  • sw $s1, 0($s0) # $s1 has data to push
  • add $s0, $s0, 4
  • POP
  • sub $s0, $s0, 4
  • lw $s1, 0($s0)
  • 41Stack Implementation
  • A stack could instead be implemented such that the stack pointer points to a FULL location at the top of the stack.
  • spsp(initial state)(1 item on stack)42Stack Implementation
  • PUSH operation:
  • add $s0, $s0, 4
  • sw $s1, 0($s0)
  • POP operation:
  • lw $s1, 0($s0)
  • sub $s0, $s0, 4
  • The stack would “grow” from the end of the array towards the beginning.
  • 43System Stack
  • Gives the programmer an “infinite” dynamic memory.
  • OS and HW work together to provide this.
  • MIPS uses the $sp ($29) to access.
  • Starts at the high address and moves towards the smaller addresses. Why?
  • 44System Stack Examples45More System Stack Examples46Queues
  • A Queue is a FIFO (First In, First Out)
  • classic analogy is a line
  • Get in (at the TAIL)
  • wait, move up in line
  • Get out at front (at the HEAD)
  • Putting thing into queue is called ENQUEUE
  • Getting thing out of the queue is called DEQUEUE
  • It takes two pointers to keep track of the head and tail of the queue
  • Let’s use $s5 for the HEAD
  • Let’s use $s7 for the TAIL
  • 47QueuesInitial state:Head (s5), and Tail (s7)After 1 enqueue operation:XHead (s5)Tail (s7)After another enqueue operation:XYHead (s5)Tail (s7)48QueuesAfter a dequeue operation:XYHead (s5)Tail (s7)Like stacks, when an item is removed from the datastructure, it is physically still present, but correct use of the structure cannot access it.49Queues
  • Implementation of a queue
  • Storage:
  • queue: .word 0:infinity # assume infinite for now
  • .text
  • la $s5, queue # head
  • la $s7, queue # tail
  • Enqueue (item):
  • sw $t0, 0($s7) # $t0 has data to store
  • add $s7, $s7, 4
  • Dequeue (item):
  • beq $s5, $s7, queue_empty
  • lw $t1, 0($s5)
  • add $s5, $s5, 4
  • How to add overflow, underflow detection?
  • 50Q[7]Q[0]Q[1]Q[6]Q[5]Q[2]Q[4]Q[3]Circular Queues
  • To avoid infinite array, wrap around from end tobeginning.
  • Head == Tail means empty
  • Head points to first item (for next dequeue)
  • Tail point to empty location (for next enqueue)
  • Head & Tail pointersExample of an 8 element circular queue51Circular QueuesHeadAfter pushing one elementXTailHeadAfter pushing another elementXYTail52Circular QueuesAfter popping an elementHeadXYTail53Circular Queues
  • Storage and initialization:
  • queue: .word 0:queue_size
  • queue_end: .word queue+4*queue_size
  • la $s5, queue # head
  • la $s7, queue # tail
  • Enqueue (item)
  • sw $t0, 0($s7) # data to enqueue is in $t0
  • add $s7, $s7, 4
  • la $t1, queue_end
  • blt $s7, $t1, continue1
  • la $s7, queue # wrap around
  • continue1:
  • 54Circular Queues
  • Dequeue (item):
  • beq $s5, $s7, queue_empty
  • lw $t0, 0($s5)
  • add $s5, $s5, 4
  • la $t1, queue_end
  • blt $s5, $t1, continue2
  • la $s5, queue # wrap around
  • continue2:
  • How to add overflow, underflow detection?
  • 55Modulo for Queues56Queue Examples57Summary of data structures
  • All data structures are based on the simple array.
  • 2D Arrays, Stacks, Queues.
  • It is all about the implementation.
  • Bounds checking is important.
  • If not documented can become confusing.
  • 585960
    Related Search
    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks