跳至主要內容

Internal Memory

Hirsun大约 46 分钟

Internal Memory

Recap

Internal memory: Cache

  • why? -- locality of references: CPU tends to access clusters of data at certain time「为什么? -引用的位置:CPU倾向于在特定时间访问数据集群」
  • the introduction of fast but small memory (Cache) between CPU and main memory「在CPU和主内存之间引入快速但较小的内存(Cache)」
  • mechanism: dynamically copy clusters into Cache -- virtually, we are using fast and large memory「机制:将集群动态复制到Cache中-实际上,我们正在使用快速且大容量的内存」

Design elements of Cache

  • mapping function: how to map blocks to cache lines
    • direct mapping vs. associative mapping

other issues: replacement algorithms, writing policy, etc.

Internal Memory

"Internal": the CPU can have direct access

  • main memory, registers, cache
  • ROM (read only memory)

There are different types of internal memory, but they share some common features「内部存储器的类型不同,但是它们具有一些共同的特征」

  • implemented using semiconductor technology「使用半导体技术实现」
  • random access method 「随机访问方法」
  • cope with the speed of CPU「应付CPU的速度」

Type

image.png

Random access memory (RAM): it is a mis-use of term. All the above memory use random aceess method; however, we usually use RAM to refer to main memory「随机存取存储器(RAM):这是术语的错误使用。以上所有记忆均采用随机aceess方法;但是,我们通常使用RAM来引用主内存」

Memory Cell

Memory Cell -- the Basic Element of Memory「记忆单元-记忆的基本要素」

Despite of the memory types, all semiconductor memory cells share common properties

  • two stable states, used to represent 0 and 1「两个稳定状态,分别代表0和1」
  • can be written into (set the state)「可以写入(设置状态)」
  • can be read to sense the state「可以读取以感测状态」

Abstract Model

Three "terminals" for one cell:「一个单元的三个“终端”:」

  • Select: select the cell for read or write operations
  • Control: to write or to read
  • Data: the bit
image.png

Implementation Technologies

image.png

Capacitors「电容器」 and Transistors「晶体管」

image.png

Dynamic RAM Cells

Data is stored as the charge of capacitors「数据存储为电容器的电荷」

  • high level of charge -- 1
  • low level of charge -- 0
  • dynamic: DRAM requires periodic charge refreshing to maintain data storage (capacitors have the tendency to leak charge)「动态:DRAM需要定期刷新电荷以维持数据存储(电容器有泄漏电荷的趋势)」
image.png
  • Write: hight (low) voltage is applied to Bit line to charge the capacitor for 1 (0)「写:向位线施加高(低)电压以对电容器充电1(0)」
  • Read: charge stored in the capacitor is fed out onto the Bit line, a sense amplifier can compare the capacitor voltage to a reference value 「读取:电容器中存储的电荷被馈送到位线上,读出放大器可以将电容器电压与参考值进行比较」

Static RAM Cells

Static RAM Cells「静态RAM单元」

  • binary bit is stored using flip-flop logic gates configurations -- essentially, transistors (as switches) and voltage「使用触发器逻辑门配置存储二进制位-本质上是晶体管(作为开关)和电压」
  • static: the cell will hold the data as long as power is supplied to it (no need to refresh)「静态:只要供电,单元将保存数据(无需刷新)」
image.png
  • Four transistors (T1, T2, T3, T4) are cross connected in an arrangement that produces stable states -- represent 1/0「四个晶体管(T1,T2,T3,T4)交叉连接,产生稳定状态-表示1/0」

  • Address line uses T5 and T6 to select this cell「地址行使用T5和T6选择该单元格」

  • Read

    • stable state 1: C1 is high, C2 is low -> T1 and T4 are OFF, T2 and T3 are ON -> read high voltage from Bit line B「稳定状态1:C1为高,C2为低-> T1和T4截止,T2和T3导通->从位线B读取高电压」
    • stable state 0: C1 is low, C2 is high -> T1 and T4 are ON, T2 and T3 are OFF -> read low voltage from Bit line B
  • Write

    • Apply high voltage (1) or low voltage (0) to Bit line B --> force the transistors into the proper states --> corresponding stable states「稳定状态0:C1为低电平,C2为高-> T1和T4导通,T2和T3截止->从位线B读取低电压」

DRAM vs. SRAM

  • Common
    • volatile -- need continuous power「常见:易挥发-需要持续供电」
  • Difference
    • DRAM cell is simpler and smaller, thus denser (more cells per unit area) and less expensive「DRAM单元更简单,更小,因此密度更高(每单位面积更多的单元)且价格更低」
    • however, DRAM requires the supporting refresh circuitry「但是,DRAM需要支持的刷新电路」
    • DRAM tends to be favored for large memory requirement「DRAM倾向于满足大内存需求」
    • DRAM for main memory, SRAM for cache

Read-Only Memory (ROM)

ROM characteristics「ROM特性」

  • contains permanent data that cannot be changed (cannot write) -- not exactly, depending on the types of ROM「包含无法更改(无法写入)的永久数据-不完全取决于ROM的类型」

  • data are burned into the chip during fabrication process -- relatively large fixed cost, and there is no room for error「数据在制造过程中被烧入芯片-固定成本相对较高,并且没有错误余地」

  • nonvolatile, no need for continous power「非易失性,无需持续供电」

Special Types of ROM

Programmable ROM (PROM)

Programmable ROM (PROM)「可编程ROM(PROM)」

  • like ROM, it can be written into only once (after fabrication process)
  • customers can use special equipment to electrically write once
  • idea: each bit is locked by a fuse; initially all 1's in the chip, if burn the fuse, change 1 to 0 (write once)
image.png

Read-Mostly Memory

Read-Mostly Memory (a variation of ROM「ROM的变体」)

  • we can re-write the memory, but at a higher cost「我们可以重新写入内存,但是成本更高」
  • useful for applications in which read operations are far more frequent then write operations, but for which nonvolatile storage is required「对于读操作比写操作更频繁但需要非易失性存储的应用程序很有用」
  • three common types: EPROM, EEPROM, flash memory「三种常见类型:EPROM,EEPROM,闪存」

Erasable Programmable ROM (EPROM)

Erasable Programmable ROM (EPROM)「可擦可编程ROM(EPROM)」

  • before a write operation, all the storage cells must be erased to the same initial state by exposure to ultraviolet radiation「在写操作之前,必须通过暴露在紫外线下将所有存储单元擦除到相同的初始状态」
  • then write electronically「然后用电子方式写」
  • read -- exposure – write「阅读-曝光-写」
    erasable: through exposure (could take 20 mins)「可擦:通过曝光(可能需要20分钟)」
    more flexible than PROM「比PROM更灵活」

Electronically Erasable Programmable ROM (EEPROM)

电子可擦可编程ROM(EEPROM)

    • updates (write operations) happen at byte level (not entire chip)「更新(写操作)发生在字节级别(不是整个芯片)」
    • however, write operation takes considerably longer than read (several hundred microseconds per byte)「但是,写操作要比读操作花费更长的时间(每字节几百微秒)」
    • more expensive and less dence (fewer bits per chip) than EPROM「比EPROM更昂贵,更省钱(每个芯片上的位数更少)」

Flash Memory

  • intermediate between EPROM and EEPROM「EPROM和EEPROM之间的中间层」
  • erasure at block level (compred to byte-level and chip level)「块级别的擦除(与字节级别和芯片级别相比)」

Summary of ROM

image.png

Chip Logic

Semiconductor memory comes in package chips「半导体存储器包含在封装芯片中」

  • each chip contains an array of memory cells「每个芯片包含一个存储单元阵列」
  • essential「基本」 task: provide address to chip, and access bits「基本任务:提供芯片地址和访问位」

how to organize and wire the cells in chips to satisfy the needs for addressing「如何组织和连接芯片中的单元以满足寻址需求」

image.png

Key issue: how to group cells into a logical piece of data「关键问题:如何将单元格分组为逻辑数据」

  • how many bits to read/write at a time
  • one extreme: 1 bit a time「一个极端:一次1比特」
  • the other extreme: one word a time (word: the unit for data processing in CPU)「另一个极端:一次一个字(字:CPU中用于数据处理的单位)」
  • in between: k bits for one chip, combine multiple chips to get a word (example later)「介于两者之间:一个芯片的k位,合并多个芯片得到一个字(后面的示例)」

Simple Example of 64 Cells

Read/Write 1 bit a time (logical data unit = 1 bit)「一次读/写1位(逻辑数据单元= 1位)」

  • each cell needs to have an address「每个单元都需要有一个地址」
  • 64 = 2^{6}, we need 6 address lines「64 = 2 ^ {6},我们需要6条地址线」
  • remember decoder? we can use a 6-to-64 decoder「还记得解码器吗?我们可以使用6到64的解码器」
  • 6 input address lines, 64 output select lines -- each is connected to the select terminal of the cell「6条输入地址线,64条输出选择线-每条连接到单元的选择端子」
  • in the chip package, 6 address pins, 1 data pins「在芯片封装中,有6个地址引脚,1个数据引脚」
image.png
  • we also need to consider the memory access cyles「我们还需要考虑内存访问周期」
  • in each cycle, we provide an address to access 1 bit「在每个周期中,我们提供一个地址来访问1位」
  • 64 cycles to access 64 bits -- too slow「64个周期访问64位-太慢」

Read/Write 8 bits a time (logical data unit = 8 bits)「一次读/写8位(逻辑数据单元= 8位)」

  • cells are organized into 8 groups, each group containing 8 cells「单元格分为8组,每组包含8个单元格」
  • one group share the same address「一组共享相同的地址」
  • 3 address pins, 8 data pins「3个地址引脚,8个数据引脚」
    • 64/8 = 8
  • less memory access cycles「更少的内存访问周期」

Read/Write 4 bits a time (logical data unit = 4 bits)「一次读/写4位(逻辑数据单元= 4位)」

  • we can use two chips A and B「我们可以使用两个芯片A和B」
  • access 4 bits from A, and 4 bits from B using the same address「使用相同的地址访问A的4位和B的4位」
  • together, it is like accessing 8 bits one time「在一起,就像一次访问8位」
  • more flexible for different processors「对于不同的处理器更加灵活」
  • the size of the logical data unit is a key design parameter「逻辑数据单元的大小是关键设计参数」

Example of 16-Mbit DRAM

It is implemented using four 4Mbit memory components

Each 4 Mbit component is a 2048 x 2048 square of cells (2^22 bits)「每个4 Mbit分量是一个2048 x 2048平方的单元格(2 ^ 22位)」

image.png

Use address to locate (select) the cell「使用地址查找(选择)单元格」

  • 2048 x 2048 square of cells = 2^{22} cells, intuitively「凭直觉」, we need 22 address lines
  • however, there are only 11 address pins (A0 – A10)
  • solution: use an external select logic (a multiplexer), where input is the 22 address lines and output is the 11 address pins「解决方案:使用外部选择逻辑(多路复用器),其中输入是22条地址线,输出是11条地址引脚」
  • effect: divided the 22 address lines into 2 groups, which are fed into the chip through 11 address pins separately「效果:将22条地址线分为2组,分别通过11个地址引脚馈入芯片」

Use address to locate (select) the cell「使用地址查找(选择)单元格」

  • 11 row address lines/11 column address lines「11行地址线/ 11列地址线」
  • use another two pins to indicate: RAS (row address select) and CAS (column address select)「使用另外两个引脚指示:RAS(行地址选择)和CAS(列地址选择)」
  • then, use can use a 11-to-2048 decoder to select the corrsponding row and column --> locate a cell in one square「然后,可以使用11到2048解码器选择相应的行和列->在一个正方形中定位一个单元」
image.png

Read/Write operation

  • 4 data lines (pins, D1 - D4), each connecting to one square「4条数据线(引脚D1-D4),每条连接到一个正方形」
  • write: apply high/low voltage to the data lines to charge the capacitors「写:向数据线施加高/低电压以对电容器充电」
  • read: use a sense amplifier to sense the voltage「阅读:使用感应放大器感应电压」
  • two pins to control write/read: WE (write enable) and OE (output enable)「两个引脚控制写/读:WE(写使能)和OE(输出使能)」
  • we can use multiple Chips to read/write a word at a time depending on the processor「我们可以使用多个芯片一次读取/写入一个word,具体取决于处理器」

Summary of Chip Logic

Current technology:

  • we can make very large capacity in a very small area「我们可以在很小的区域内制造很大的容量」
  • however, the limit is bounded by the physical space needed for pins -- careful design to save number of pins is important「但是,该限制受引脚所需的物理空间限制-谨慎设计以节省引脚数很重要」

Chip Logic considerations「芯片逻辑注意事项:」:

  • determine the number of data pins (how many bits to read/write at a time)「确定数据引脚的数量(一次读取/写入多少位)」
  • determine the number of address pins (need consideration of address multiplexing)「确定地址引脚的数量(需要考虑地址多路复用)」
  • need for additional buffers and controls「需要额外的缓冲区和控件」
  • layout and wiring need to consider heat distribution (data pins are distributed on the two sides of the chip)「布局和布线需要考虑热量分布(数据引脚分布在芯片的两侧)」

Memory Errors

  • Hard Failure
    • permanent physical defect to cells「永久的硬件损坏」
    • replacement「替代以修复」
  • Soft Error
    • content of the cell is modified, due to random, nondestructive event「由于随机,非破坏性事件,修改了单元格的内容」
    • the function of cell is still OK「单元格的功能还是好的」
    • example: the charging to the capacitor is not sufficient: 1 -> 0「比如电容器充电不足导致1->0
  • Error Detection
    • knowing that there are errors in a block of data
  • Error Correction
    • detect, and recover the correct contents「检测并恢复正确的内容」
    • correction is harder than detection「校正比检测难」
      • example: we know there are an even numuber of 1's in the data (detection is easy); detection is hard: there could be multiple combinations of errors「例如:我们知道数据中的偶数为1(检测很容易);检测很难:可能有多种错误组合」

Coding Theory

Coding theory itself is a fruitful field of study「编码理论本身是一个富有成果的研究领域」

general idea: use redundancy to encode the conditions for which correct data should satisfy -- redundancy is a function of original data: K = f(M)「总体思路:使用冗余编码正确数据应满足的条件-冗余是原始数据的函数:K = f(M)」

image.png

Framework of Error Correction

Framework of Error Correction「纠错框架」

image.png

Example: Hash Functions for Error Detection

image.png

Encode for check

Warm-up: single parity code

  • original data block M has 7 bits (abuse of term, M = 7)「原始数据块M具有7位(滥用项,M = 7)」
  • attach a single bit K to the end of block (K=1)「将单个K附加到块的末尾(K = 1)」
  • the code thus has 8 bits, M|| K --- this is a simple encoding process
    given M, we need to decide K「该代码因此具有8位,M || K-这是一个简单的编码过程」

Enconding rule

  • function W(D) = number of 1's in data block D
  • Rule: add K such that W(M||K) is even (even parity)「规则:加K使得W(M || K)为偶数(偶数)」
  • example
    • M = 000 0011, W(M) = 2 -> set K = 0
    • M = 110 0111, W(M) = 5 -> set K = 1
  • we also could have odd parity「我们也可能有奇偶校验」

One Error Detection

The single parity code is able to detect one error「单一奇偶校验码能够检测到一个错误」

  • suppose the stored data is D, we can compute W(D)「假设存储的数据为D,我们可以计算W(D)」
  • if W(D) is even --> no error; else one error「如果W(D)是偶数->没有错误;否则一个错误」
  • note that the above detection algorithm relies on one essential assumption: there is at most one error 「请注意,上述检测算法基于一个基本假设:最多存在一个错误」
  • also note that, we can only detect error, we do not know the position of the error (cannot correct the error)「还要注意,我们只能检测错误,我们不知道错误的位置(无法纠正错误)」

Example

  • suppose M = 000 0011, W(M) = 2 --> K = 0
  • store M||K = 000 0011 0 in the storage device
  • some time later, we check this data block D by computing W(D)
  • suppose W(D) = 3 --> error: e.g., 000 0111 0 or 000 0011 1
  • suppose W(D) = 2 --> correct; but could also be 000 0101 0 (two errors, we assume that this could not happen)

The Essence

essence「精华」

we are using 1 redundant bit to encode two cases:

  • case 1: no error
  • case 2: 1 error

question: can we extend this idea to general error-correcting code?

Correct

General Case

Consider one error correcting code

  • original data M bits, redundancy K bits; together N = M + K bits「原始数据M位,冗余K位; N = M + K位」
  • again, we assume that there is at most one error「再一次,我们假设最多有一个错误」

Our goal is to correct one error (if happens) -- in other words, know the position of the error「我们的目标是纠正一个错误(如果发生)-换句话说,知道错误的位置」

there are a total of (N+1) cases. Why?「共有(N + 1)个案例。为什么?」

(N+1) cases:

  • case 0: no error

  • case 1: error at position 1

  • case t: error at position t

  • the essence of error correction code: use K bits to encode (N+1) cases「纠错码的本质:使用K位编码(N + 1)种情况」

  • relation: 2^{K} >= M + K +1「关系:2 ^ {K}> = M + K +1」

  • coding theory deals with the realization of the above encoding process using mathematical tools「编码理论使用数学工具处理上述编码过程的实现」

Overhead: K/M, which is the redundancy「冗余」 ratio「率」「开销:K / M,即冗余率」

  • M = 4 -> K = 3 ( 2^3 = 8 >= 4 + 3 +1); K/M = 3/4
  • M = 8 -> K = 4 ( 2^4 = 16 >= 8 + 4 +1); K/M = 4/8
  • M = 16 -> K = 5 ( 2^5 = 32 >= 16 + 5 +1); K/M = 5/16

as M increases, the overhead decreases「随着M的增加,开销减少」

So, is M the larger the better?

  • unfortunately, no
  • remember the fundamental assumption: at most one error「记住基本假设:至多一个错误」
  • as M increases, the probability of having more errors also goes up「增加」「随着M的增加,出现更多错误的可能性也会增加」

Case Study: (7-4) Hamming Code

Hamming Code「海明码」、parity bits「奇偶校验位」

  • the classical one-error correction code, with (7-4) the most common setting「经典的-纠错码,最常见的设置是(7-4)」
  • N = 7, M = 4 (original data), K = 3 (redundancy bits)
  • we will not dig into「深入研究」 the mathematical「数学的」 details「我们不会深入研究数学细节」
  • similar to single parity code, however, we now use three parity bits「与单个奇偶校验代码相似,但是,我们现在使用三个奇偶校验位」
  • data bits: d1, d2, d3, d4「数据位:d1,d2,d3,d4」
  • parity bits: p1, p2, p3, where each parity bit "cover" 3 data bits「奇偶校验位:p1,p2,p3,其中每个奇偶校验位“覆盖” 3个数据位」
image.png
  • p1: cover d1, d2, d4, that is, number of 1's in p1||d1||d2||d4 should be even
  • p2: cover d1, d3, d4
  • p3: cover d2, d3, d4
Example
image.png
More

Not Required

image.png
The code words
  • there are a total of 16 valid code words (why? 4 "free" data bits)「共有16个有效代码字(为什么?4个“空闲”数据位)」
  • the Hamming distance between every two code words is 3「每两个代码字之间的汉明距离为3」
  • Hamming distance: the number of different bits「汉明距离:不同位数」
  • this examples why Hamming code can correct 1 error「这个例子为什么汉明码可以纠正1个错误」
image.png

批注:不明白在说什么......

引用

  • COMP2421@PolyU PowerPoint