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

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

Implementation Technologies

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

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需要定期刷新电荷以维持数据存储（电容器有泄漏电荷的趋势）」

• 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)「静态：只要供电，单元将保存数据（无需刷新）」

• 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)

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

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「如何组织和连接芯片中的单元以满足寻址需求」

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个数据引脚」

• 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位）」

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解码器选择相应的行和列->在一个正方形中定位一个单元」

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）」

Framework of Error Correction

Framework of Error Correction「纠错框架」

Example: Hash Functions for Error Detection

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个数据位」

• 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

More

Not Required

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个错误」

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

引用

• COMP2421@PolyU PowerPoint