CCE Computer Memory

Size: px

Start display at page:

Download "CCE Computer Memory"

闰僪
4 years ago
Views:

1 Computer Logic II CCE 2010 Dr. Owen Casha Computer Logic II 1

2 Computer Memory Computer Logic II 2

3 Computer Memory The memory needs to be able to store many binary patterns (0 s and 1 s) arranged in words in accessible locations. For storing a program currently being executed and storing its associated data we need to be able to access any program/data location at will, in any order with high speed, i.e. the memory must be random-access. We need the capability of both reading and writing data. The maximum size of the memory that can be used in any computer is determined by the number of bits in the address: Example 16 bit address can qualify 2 16 = 64K locations. Computer Logic II 3

4 Memory Organization The memory is organized in words, each having a unique address. address data To access a particular location, its address must be specified and then the data written or read from or to that location. Computer Logic II 4

5 Buses Bits in a computer travel on buses, which are parallel lines of conductors which carry one bit each. There are three types of main buses in a computer architecture: The Address Bus: carrying the bits which specify the address of the required location. The Data Bus: carrying the information itself. The Control Bus: carrying control signals for the devices attached to the CPU. Buses can be directional (one direction only) or bidirectional (data travels in both directions). Computer Logic II 5

6 Memory and CPU The main memory is usually designed to store and retrieve data in word length quantities. Thus if the address bus is 32 bit wide and the data bus is 16 bit wide, then the memory may contain up 2 32 (4 Giga) addressable locations, each containing a word of 2 bytes (16 bits). Most modern computers are byte-addressable, meaning that each byte has a separate address. 2 k addressable locations Computer Logic II 6

7 Byte-addressable The smallest addressable unit in most computers is a byte rather than a word. This is most convenient since characters in a computer are encoded on 8-bits (1 byte). This means that successive addresses refer to successive byte locations in main memory, and the computer is said to be byte addressable. Thus a word length of 32 bits can accommodate 4 bytes. There are two types of address assignment schemes which state how the individual bytes are organized within a word, namely the big-endian and the little-endian schemes. Computer Logic II 7

8 Big & Little Endian If we consider a word length of 32 bits then 4 bytes can be placed in each word. Two different schemes are used to order these bytes within a word: Big-endian: bytes are numbered starting with the most significant byte of a word which is given this address. Little-endian: bytes are numbered starting at the least significant byte of a word which is given this address. Most Significant Byte Least Significant Byte Computer Logic II 8

9 Internal Organization D Flip Flop Computer Logic II 9

10 Memory Interfacing Computer Logic II 10

11 Memory mapping Computer Logic II 11

12 Memory Management The management of memory access between these types of memory is called memory management. Computer Logic II 12

13 Main-Secondary Memory Management Various memory management schemes exist to handle data between main memory and secondary memory to permit large software packages which could not reside in the main memory because of the limited available main memory. These include: Overlaying schemes Paging schemes Segmented schemes Computer Logic II 13

14 Memory Overlaying The simplest memory management method is to employ overlaying in which programs or sections of programs are transferred into the main memory as required, overwriting existing programs. Each transfer is specifically programmed. Involves diving a large program into a main file and one or more overlay files. The overlay files would be called from within the main file, and would typically overwrite the main file when transferred. This process would be repeated with other files. Places heavy burden on programmer, difficult debugging and cause disk trashing (excessive disk transfers). Computer Logic II 14

15 Memory Overlaying Scheme Computer Logic II 15

16 Paging Scheme Automatic process for transferring blocks into and out of the main memory, relieving burden from the programmer, and preferably predict blocks likely to be required in future. The memory space is divided in blocks. Typically of 128 to 1024 words each. Each address is composed of 2 parts, a page number and a line number. Page numbers are concatenated with line number to form the complete address. The term virtual (paged) memory is used to describe this system. Computer Logic II 16

17 Virtual and Real Addresses The actual address in memory (the actual bit pattern going in the memory chip) is called the real address and the program address (the one specified by the program) is called the virtual address. A hardware mechanism is used to translate the virtual page number to a real page number. This mechanism operates only on the pages in main memory. If the required page is not in main memory a software program must be executed to: Find the required page in secondary memory Transfer this page into the main memory Provide space in main memory by choosing the best out block. Computer Logic II 17

18 Memory Allocation Computer Logic II 18

19 Page Swapping Computer Logic II 19

20 Address Translation There are two basic hardware methods to translate the virtual page address into a real page address: Direct Mapping: All real page addresses are stored in a high speed RAM, in locations whose addresses are the virtual addresses of the associated real addresses. Associative Mapping: A special type of memory, associative memory (or content addressable memory CAM), is used, in which a location is identified by its contents rather than by an assigned address. The binary word applied to the data inputs of the CAM is compared with all stored words, generating an appropriate signal if a match is found. This memory is coupled with a normal RAM which outputs the real page address. Computer Logic II 20

21 Direct Mapping Computer Logic II 21

22 Associative Mapping Computer Logic II 22

23 Replacement Algorithms There are various replacement algorithms that can be used to select the page to remove from main memory to make room for the incoming page after a page fault: Random replacement algorithm: Page chosen in a random order. This algorithm would not be really suitable for real programs which normally access locally, i.e. in sequential order. First-In-First-Out (FIFO): The page existing in the main memory for the longest time is transferred out. First-in-not-used-first-out: Replaces the oldest page which has not been used recently. Least recently used: The page which has not been used for the longest time is transferred out. Computer Logic II 23

24 First-In-First-Out Computer Logic II 24

25 Algorithm Implementation Computer Logic II 25

26 First-In-Not-Used-First-Out Computer Logic II 26

27 Algorithm Implementation Computer Logic II 27

28 Least Recently Used Computer Logic II 28

29 LRU Algorithm On page reference: If page is present in main memory Set its counter to 0 Increment all counters originally less than that of the referenced page On page fault: If main memory is full: The page with counter = max is replaced with the new block of counter 0 Increment all other counters If main memory is not full: Clear counter of new page Increment all other counters Difficult to implement max is the number of pages in main memory - 1 Computer Logic II 29

30 Use bits, counters and protection bits The use bit of each page, if necessary for the replacement algorithm, is incorporated in the hardware translation table. Counters used in the LRU replacement algorithm are very difficult to implement in practice, since a counter would be needed with every page in main memory. Additionally a protection bit is needed in the translation table to make pages read only or to prevent a page being removed from the main memory if the page is part of an active user program in a multiprogramming environment. Computer Logic II 30

31 Page Size Considerations Page size is typically 512 words. If a smaller page is chosen: Time taken to transfer pages from main to secondary storage is shorter A large selection of pages resides in main memory However it necessitates a large page table For larger pages: Time taken is longer A small page table is needed The unused space at the end of each page is likely to increase (This is known as internal fragmentation). The number of words per page chosen is a compromise. Computer Logic II 31

32 Segmented Systems Memory space is not divided into equally sized pages but into variable sized blocks of contiguous locations called segments. Each address is composed of a segment number and a displacement within the segment (offset). Logical address is here used to describe virtual address and physical address refers to the real address. Rather than concatenate the two, the offset and the segment are added together to form the physical address. Segments can be shared between programs and are allowed to partially overlap if required. Computer Logic II 32

33 Address Translation Processor Virtual Address Computer Logic II 33

34 8086 Example Computer Logic II 34

35 Placement Policy The replacement algorithm in segmented system can be similar to the paged system taking into account the varying size of the segments when allocating space to new segments (Placement Policy). The placement policy must maintain a list of the locations and sizes of all unallocated holes, called the hole list. segment hole Its task is to decide which hole to use, and to update the hole list after insertion minimizing the amount of hole fragmentation. This type is called external fragmentation. It has also the additional task of compacting the segments, for creation of space when needed. Computer Logic II 35

36 Placement Policies Numerous placement algorithms exist, the three principal ones being: Best fit: choosing the hole which most exactly houses the entering segment. Worst fit: choosing the hole which leaves the most space for further placement. First fit: the first available hole is chosen. There are also some modifications to these policies which do not permit the creation of holes which are too small to be of any use. Computer Logic II 36

37 Best Fit Computer Logic II 37

38 Worst Fit Computer Logic II 38

39 First Fit Computer Logic II 39

40 Processor-Main memory management Processor performs operations much faster than the access time of the main memory. There exist faster memories, but their cost does not make it economically viable to make the entire memory of these fast memories. This problem can be alleviated by introducing a small block of high-speed memory called a cache between the main memory and the processor (or internally to the Processor). Computer Logic II 40

41 Principle of Locality Temporal locality: Recently referenced items (instructions or data) are likely to be referenced again in the near future: Iterative loops, subroutines, local variables. Working set concept Spatial locality: Programs access data which is near to each other Operations on tables or arrays Cache size is determined by spatial locality Sequential locality: Processor executes instructions in program order Branches or in sequence Computer Logic II 41

42 Access Time Suppose that a word get referenced n times: Average access time = (M + n x m)/n Where M is the main-memory to cache transfer time n is the number of references made to memory m is the time to access the cache Assuming that it is necessary to first reference the cache before a reference to main memory is made to fetch a word. It may also be to make a second reference to cache after the word is read, though the word can be sent simultaneously to cache and processor. Altered cache locations must be sent back to main memory on replacement. This reduces the average access time. Computer Logic II 42

43 Memory Interleaving Main memory is interleaved to match the speed of the cache. The main memory is divided into a number of independent modules in such a way that words from different modules can be transferred in parallel to cache and applications. Normally, the number of modules is a power of two to simply addressing. The number of modules is chosen to produce a suitable match to the speed of operation of both memories: if for instance the cache is 50 ns and the main memory is 200 ns then 4 memory modules are interleaved. Computer Logic II 43

44 4-module memory interleaving Computer Logic II 44

45 Hits and Miss The probability that the required word is already in cache depends upon the program and its locality of reference. Typically 80-90% of references will find their words in the cache. A hit occurs when a location is immediately found in cache, otherwise a miss occurs, and a reference to the main memory is necessary. The hit ratio is defined as: Hit Ratio= Number of times the required word is found in cache Total number of references Computer Logic II 45

46 Mapping Schemes The problem of mapping information held in main memory into the cache is similar to main-secondary virtual memory systems, though any cache mapping scheme must be totally implemented in hardware to achieve improvements in the system operation. Various strategies are possible: Direct mapping Fully associative mapping Set-associative mapping Computer Logic II 46

47 Direct Mapping In this scheme, block j in memory maps onto block j modulo n in cache, where n is the number of blocks in cache. Since more than one memory block is mapped onto a given cache block position, contention may arise for that position even when the cache is not full. Thus although the block in cache can be traced directly from the block number, and very easy to implement, the system is not flexible. Computer Logic II 47

48 Direct Mapping Scheme Computer Logic II 48

49 Direct Mapping Example Computer Logic II 49

50 Direct mapping address translation Computer Logic II 50

51 Fully Associative Mapping This is a much more flexible mapping scheme, in which the memory block can be placed in any cache block position. Thus the cache space can be used more efficiently because replacement only takes place when the cache is full. In this case we need a replacement algorithm since now the choice of which cache position is to be replaced is not fixed. The cost incurred using this scheme, is that since the block could reside anywhere in the cache, all the tags in the cache to verify its presence. Computer Logic II 51

52 Fully Associative Mapping Computer Logic II 52

53 Fully Associative Mapping Example Computer Logic II 53

54 Fully Associative Mapping Address Translation Computer Logic II 54

55 Set Associative Mapping This is a combination of direct- and fully associative mapping. Mapping scheme allows that any main memory block can reside in any cache block of a specific set of blocks. Hence, the contention problem of direct mapping is eased by having a few choices of block placement. On the other hand a small-way associative search is simple to implement: Computer Logic II 55

56 Set Associative Mapping Computer Logic II 56

57 Set Associative Mapping Example Computer Logic II 57

58 Set Associative Mapping address translation Computer Logic II 58

59 Write mechanisms on replacement If the processor writes to the copy of memory in cache, it is necessary to maintain both the cache and the main memory copy identical for consistency. There are two mechanisms to update the main memory during a memory write instruction: Write-through: every write operation to the cache is repeated to the main memory. This is inefficient if the cache copy is written to several times before it is replaced to main memory. Write-back: The write operation to the main memory is only done at block replacement time. Computer Logic II 59

60 Further Reading Digital System Design: Barry Wilkinson & Rafik Makki, Prentice Hall Chapter 10. Computer Organization: V. Carl Hamacher, Zvonko G. Vranesic, Safwat G. Zaky, McGraw-Hill International Editions Chapter 5 Computer Logic II 60

穨control.PDF

穨control.PDF TCP congestion control yhmiu Outline Congestion control algorithms Purpose of RFC2581 Purpose of RFC2582 TCP SS-DR 1998 TCP Extensions RFC1072 1988 SACK RFC2018 1996 FACK 1996 Rate-Halving 1997 OldTahoe