Memory Flashcards
What is a logic level?
In analogue, 1s and 0s are divided by a threshold voltage. SO whilst 0 and 1 are convenient abstractions they do not reflect reality.
What are the main criteria for designing a memory system?
Rapid data access and it should take as little space as possible.
What assumptions must be made to model digital discrete circuits as networks?
The nodes are unidirectional, instantaneous, isopotential nets interconnecting devices.
How are digital ‘networks’ analysed?
Events (logic transitioned) are generated on the outputs at some future date in response to events asserted on the inputs.
As such analysis is centred on an event queue; a list of events ordered by time.
How is the system state of a discrete system represented?
The state can be summarised as the logic values in the nets and the event queue, i.e. events that will happen.
What happens when you assert an input?
Logic values don’t propagate instantaneously, although there will be an output change, for a brief time, the event is hidden from the device, but it is still part of the stae.
How are logic drivers modelled?
Logic drivers can be modelled as a voltage source with an ‘internal’ impedance.
What effect does modelling the driven gate as a resistor have?
Since the driven gate is a resistor, it means that the voltage value on the interconnect is loaded. This means that if multiple gates read from the same interconnect, they may pull down the voltage value, leading to a misrepresentation of the intended logic value.
What does fanout measure?
Fanout is a measure of the max number of gates an output can drive before the voltage value is pulled down to the point where the voltage may be incorrectly read.
What happens when interconnects are driven at high speeds?
The interconnect begins to behave more like a transmission line, The signal can be sent, reach the destination and reflect. The reflected signal returns after bouncing off the origin leading to a second logic event.
What is the forbidden zone in circuits?
The forbidden zone refers to either
(0threshold < V < 1threshold)
Or,
out of range (< 0V or > Vcc)
How does CMOS deal with voltages in the forbidden zone?
CMOS devices appear to behave as simple threshold devices so it can be assumed that voltages less than 0 are treated as logic ‘0’ whilst voltages greater than 1<strong>threshold</strong> are treated as logic ‘1’. For voltages in between manufacturers make no promises.
How does TTL deal with the forbidden zone?
Holding the voltage at 1V will lead to a 1MHZ oscillation on the output, the exact value depends on the system
Thus max transit time, may be specified, as a measure of how fast you are expected to transit through the zone.
Describe the logic states high and low
These are ‘disconnected but still have a value’.
They are capable of being read, like a 0 or 1, but will not fight if connected to a forcing
value. 0, 1, and X are the low impedance equivalents of L, H and Z.
Describe how the effective output impedance relates to logic values?
The effective output impedance of the driving gates: for ‘0’, ‘1’ and ‘X’, Rforce is as low as can be made practical; the corresponding fanout is high because the low value of Rforce allows Vhigh (or Vlow) to be asserted easily on the driven gates. For ‘H’, ‘L’ and ‘Z’, the output impedance (Rweak) is quite high so that if any other gate asserts a ‘0’ ‘1’ or ‘X’, it easily overcomes the high impedance
version.
How are events generated?
Outputs are generated in response to changes on inputs
How do you determine the difference between 1 and high?
To detect the difference between ‘1’ and ‘H’, . You have to have some means of loading the signal and measuring
d(signal)/d(load).
As measuring the voltage is insufficient to tell the difference.
Describe high impedance Z in computing
The voltage value is usually stored on some parasitic capacitance and will decay with time. This might sound a
bit tenuous, but it is the fundamental underlying physical principle of DRAM.
A ‘control’ or bus-driver gate have (conventional) data inputs, plus a ‘control’ input, which may be used to put the output into a high impedance state.
Describe the conflict logic state
This is an abstract logic state that unambiguously indicates a problem. It may be derived, for example, if two non-high impedance gates are connected together.
If they both assert the same value, there
is no problem: the drive capability is increased, If the two gates attempt to assert different low-impedance states (‘0’ and ‘1’, for example), then the resultant logic value will depend on the relative values of the two output impedances, but more importantly the current flowing through the two output circuits can
be arbitrarily high - the physical behaviour goes way outside the modelling intent, and in
some logic families device destruction will result. Even if a device can withstand such an insult transiently, the lifetime will be considerably compromised. Ideally, a simulation would tell you this.
Describe X (Don’t Know) State
This is a low-impedance signal (forcing) but we don’t know what the value is. Again, it cannot occur in reality - a ‘0’ is a ‘0’, a ‘1’ is a ‘1’, but a ‘X’ will be either a ‘0’ or a ‘1’.
Its existence may or may not indicate a problem; if it propagates through a system it is indicative of subtle (i.e. bad) design.
Like the conflict, you cannot measure it directly, but
also like the conflict, you want to know if you have one.
Describe U, uninitialised
This is again something you cannot measure in reality, it is a way for a
simulation to say “nothing that has ever happened has caused me to compute a value for
this signal”. Which begs the question “why is it here?”
Should you have more logic states?
Yes, VHDL has eleven distinct logic states, for example - but the more states, the more information you can extract about your design, for only a modest increase in compute.
What is the source of the Z persistence?
Most of the ‘unseen’ components that make up a system - nets, pins and so on -have a
parasitic capacitance associated with them. This capacitance stores charge which is the source.
Effect of capacitance on alogic driver
To assert a logic value usually means the driver has to
inject or remove that charge. This takes time and requires energy. It is easier, from a practical perspective, to produce a driver that is good at either injection or removal, as opposed to both.
What are the goals for memory design
- To make the user believe processes are executing simultaneously
- To make each process appear infinite memory is available and can be accessed infinitely quickly.
Describe the memory hierarchy
The memory hierarchy refers to the order of primacy for memory, i.e. which memory is used first..
Disk→Memory→Cache→Register
What is swapping in Memory?
• The OS stores a queue of processes waiting to
execute.
• As space becomes available, processes are loaded.
When a process finishes, it is removed.
• A process may be swapped out if stalled (e.g.
waiting for I/O).
Describe the idea of optimum swapping
Optimum swapping refers to maintaining a balance between too little and too much swapping. Too much and the processor is spending too much time with memory transfers.
Too little, stalled processes aren’t removed at the correct time.
What is partitioning?
Partitioning is simply a method of splitting memory into pieces. There are two types, fixed size and variable size.
Describe Fixed Size Partitioning
Fixed-size memory partitions: Easy to administer (logarithmic distribution is usually best)
Describe Variable Size Partitions
Variable-size memory partitions:
Memory allocated as required.
Fragmentation makes it harder to load incoming
processes
This leads to memory wastage..
Define Process Topology
Refers to what processes are running at what time.
Describe Physical Address
Physical addresses refer to absolute locations in memory.
Describe Logical Addresses
Logical addresses are relative to the address of the beginning of the program.
What is paging?
Paging is the process of dividing the memory of a process into fixed-size pages. Whilst physical memory is in turn divided into frames.
How are pages mapped onto frames
Pages can be mapped non-contiguously to
frames, and so does not result in memory gaps, unlike with partitioning.
Noncontiguous meaning, not placed in a consecutive manner.
Pages and Logical Addressing
Logical Addressing is more complicated, as
• For a process, a single offset is not enough anymore.
• Each process has a page table.
• Logical addresses now refer to a page, and the page table
translates the base address (logical page) to the physical
address (frame)
Why are page tables useful?
They are vital for logical addressing. As processes are divided into multiple pages. Pages that require a corresponding logical address for safe storage.
How is swapping used with pages?
Pages, not processes, are swapped in and out.
Thus, we’ve created the illusion of “infinite” memory, from the perspective of the process.
However, a paging supervisor is required for controlling swap rate.
Describe Mapping Logical to physical addressing
Logical addresses, which are used by software to reference sections of memory used by a process, function. differently in a paging system.
Logical addresses refer to a page number, which is used as a key in the page table.
The page table identifies the frame, from which a base address can be derived. The base address is combined with the offset to obtain the full physical address.
What is Page Thrashing? Why is this bad?
Page thrashing is when page faults happen too often. This refers to when a process wants a page that has been
swapped out. The OS needs to go fetch it.
This is a problem as the processor spends
a lot of time re/mapping pages to frames, as opposed to computing.
Page Table is Swapped Out
One method is, each logical memory access can require two physical accesses:
1st search through memory if page table is swapped out
Then, look up data using page table, however, this method is slow so, Translation Lookaside Buffer(TLB) is used.
The TLB is a cache that stores page table entries.
What is the Translation Lookaside Buffer?
Cache which stores recent page table entries used as pages can be swapped out.
Purpose of virtual memory
To pre-emptively get the required data into the
most accessible place, without
the user having to care.
Where can a page table be?
- The TLB
- Main memory
- Disk
Where can the data be stored in?
- Memory cache
- Main memory
- Disk
Describe Segmentation
Segmentation is another memory management mechanism
The application splits memory into segments of variable size at compile time (unlike paging, where the user only sees one
contiguous block).
• The compiler produces addresses of the form {segment,oset}
• The linker reconciles this with the memory subsystem.
• Each segment has different access writes and privileges:
- Processes can be run in isolation, safely. (Segmentation Fault)
- Self-modification can be prevented (Harvard).
- Data/cache can be shared between processes.
How common is segmentation
Most x86 machines use segmentation with paging.
How is segmentation implemented with paging?
Segmentation can be combined with paging. The compiler divides the program into segments at compile time, and the paging supervisor divides each segment into pages at run time.
A page table exists for each segment,
and entries are stored in the translation lookaside buer as before
Aims of Cache Systems
• Provide access speed close to that of the fastest
memory.
• Provide capacity close to that of the most
capacious memory.
• The cache contains a local copy of parts of the
main memory.
• If the CPU wants some memory in the cache, it is
returned quickly.
• If the CPU wants some memory, not in the cache,
the cache fetches it.
What do caches store?
The cache contains a local copy of parts of the
main memory.
Are there levels to cache?
Yes, the levels of caches depend on access speed and memory size.
Structure of Memory Vs Cache
Memory is divided into blocks
Caches are divided into lines
Blocks and lines both store words.
We assume lines and blocks are the same sizes.
Each line has a tag corresponding to a block.
Memory has more blocks than the caches have lines
Can caches be filled and fetched from at the same time?
Yes, caches can be filled and fetched form in parallel as they typically involve different processes.
Are cache misses errors?
No, at times they must happen such as the first time a program or process is run. As if not run before then the process will not be stored in the cache.
Are caches always shared?
No, caches are often split into levels based on the speed of access and size of memory.
In addition, these levels may be divided into instruction caches and data caches.
Define Block in memory
Block: A set of words in main memory.
Define Line in Memory
Line: A tagged entry in the cache, which holds a set of words.
Define tag in memory
Tag: An ld associated with the cache line and its contents.
Define cache hit
Cache hit: Process wants to read from memory, and the cache has
it, resulting in a faster lookup compared to a cache miss.
Define Cache Miss
Cache miss: Process wants to read from memory, but the cache
does not have it, so the cache has to fetch it, resulting in a slower
lookup than a cache hit.
Why are caches separated?
In part because different processes require different access patterns. As such more efficient for different caches to correspond to different access patterns. Caches can be designed based on the type of instruction used for the cache.
What are tradeoffs to consider for caches
Should the cache behave more like a register or memory, i.e. access speed vs storage size
What are mapping functions?
Caches are smaller than memory, so blocks need to be mapped onto caches. A mapping function tells the cache line to which memory block is related.
There are three types:
- Direct
- Associative
- Set Associative
What is direct mapping?
• Each block of main memory maps onto only one line.
A set of blocks are designated to the same line.
Benefits and flaws of direct mapping
• Quick to calculate which line a given block should be placed in Cache line ID = Block number (in main memory) % Number of lines in the cache
• Cache Thrashing: High cache miss rate -
different blocks are addressed by the process, which
are alternately mapped and evicted. With direct mapping this can easily happen
How to break direct mapping?
To cause thrashing can make alternate references to blocks in the same set. As the blocks are never stored in the cache at the same time since each line can only hold one memory block.
What is associative mapping?
• Any block can go into any cache line.
• The tag is the address of the block that’s currently loaded.
• To check if the cache holds a block, the cache needs to
(simultaneously) compare all cache tags with the desired block address.
• Expensive lookup, but flexible for a greater variety of access patterns.
How to break associative mapping?
Break by a loop. The number of blocks in the loop should be greater than the number of lines in the cache.
What is set-associative mapping?
- Compromise between direct and associative.
- The cache is divided into a set of subcaches.
- Each memory block can go into only one subcache (ala direct), but it can into any line of that subcache (ala associative).
- As subcache size → cache size (i.e. only one subcache), the cache becomes fully associative.
- As subcache size → 1 (i.e. each subcache holds only one line), the cache becomes fully direct.
What are replacement algorithms?
Replacement Functions are used to determine which line is overwritten when a new block is loaded.
Algorithms include:
- Least recently used
- First-in, first-out
- Least frequently used
- Random
What is cache coherence?
The problem of keeping main memory and the
cache synchronised.
What is cache coherence?
The problem of keeping main memory and the
cache synchronised.
What problems are associated with cache coherence?
Read access: No problem with a single access pathway, but DMA exists.
Write access: If a cache line has been written to (dirty), it must be pushed to the main memory before it’s replaced.
What are the solutions to cache coherence?
Write Through: Update main memory whenever a cache line is written.
Write Back: Update main memory whenever a cache line is evicted.
What is write through?
- All write operations are performed in parallel.
- All modules with cache access must monitor all reads to maintain coherency. This leads to substantial memory traffic!
What is Write Back?
- When a line is modified, a “dirty” bit is set, and the main memory is only updated when a “dirty” line is replaced.
- All access through one cache.
What are the solutions to cache coherency for multiprocessor machines?
Bus watching, Hardware transparency: and Non-cacheable segments:
Describe Bus watching
A solution to cache coherency in multiprocessors
In a write-through system, any write to the main
memory causes the immediate removal of cache lines containing the clobbered data.
Describe Hardware transparency
A solution to cache coherency in multiprocessors
Used for write-through systems, each write to main memory causes an immediate update of all cache lines. Doesn’t delete and re-load entire cache.
What are non-cacheable segments
A solution to cache coherency in multiprocessors
Prevent caching of certain regions of
(shared) memory.
Large Vs Small Line Sizes
Smaller blocks/lines better exploit locality, result in more fetch/replace operations, and
have less data transfer for those operations.
Larger Lines mean less fetch operations are required however, means less lines can be used in a cache.
In general line size is between 8-32 bytes.
What is cache granularity?
How to and if to use cache levels, i.e. how to stagger cache levels.
Why use multilevel caches?
Different Caches are suitable for different processes.
Why use a unified/Split Cache?
Split meaning between instruction and data not in storage size
- Unified cache has a better overall hit rate because the code/data imbalances even out.
- For fast (pipeline) architectures, a Harvard cache eliminates data/code bus contention (in a pipeline, data and code can be requested out of order).
How do caches and virtual memory interact?
• Cache systems and virtual memory systems operate largely orthogonally to each other - the virtual
memory system exists \after” the caching system.
Addresses may be taken from the Virtual memory, however, caches are not aware of pages, they simply see memory blocks.
How do caches relate to Translation Lookaside Buffer(TLB)?
• The interactions between cache systems and the translation lookaside buer (TLB) are more complicated; either the tags in the cache hold
- physical addresses (in which case they need to be translated by the TLB prior to lookup), or
- logical addresses (in which case cache tags need to be kept in coherence with the state of the TLB)
How do disks relate to memory analysis?
- They typically have their own processor and memory.
- They also have a layered cache system - certain “bits of magnetic space” are easier to get at than others.
- Spatial locality really matters.
- They typically have their own RAM caches.
How is the response generated?
The response is generated as a sequence of events appearing on the output of each gate
How has the performance of modern systems affected the analysis of systems
Can’t as easily assume voltage signals reach gates at the same time. A difference in path length causes a significant time difference.
The voltage at receiver equation
Vr =( VwRr)/(Rw +Rr)
What happens if Rr → infinity
Vr = Vw
Rr >> Rw
What happens if Rr → 0?
Vr →0, with Rw >> Rr
How can the voltage/logic level be corrupted?
VOltage van be pulled down to 0 if Rr→0.
What is TTL?
Transistor–transistor logic (TTL) is a logic family built from bipolar junction transistors. Its name signifies that transistors perform both the logic function (the first “transistor”) and the amplifying function (the second “transistor”), as opposed to resistor–transistor logic (RTL) or diode–transistor logic (DTL).
Can boolean algebra always apply to a bus?
No, when the nodes are driven in different directions, simple ones and zeros don’t describe the outputs of the bus. SO we also observe the impedances.
What should you do if multiple sources are driving a bus?
For multiple sources sat all other drives to weak values states i.e. Rweak is high impedance, so source with low forcing impedance dominates for the bus.
What is a passive pull-up/pull-down device?
Basically, a resistor is a device that without extra Work, will pull up or pull down the voltage of the net.
Designed to have said voltage easily overwritten by active inputs to the net.
What are the benefits of passive pullup/pulldown devices?
Boost efficiency of up-down behaviour.
Allows the driver to be smaller, and more efficient as only either removes charge or only adds charge.
How are pull up/ pull down incorporated into a device?
The effect is created simply by connecting a resistor between the net and either ground (for
passive pull-down) or the supply rail (for passive pull up).
Often rather than a resistor a MOS transistor with the gate and source shorted, which requires
no extra processing steps which makes better use of the space..
How is the virtual driver designed?
1: Two inputs the same, output:=input
2: Forcing 0 and forcing 1 is a conflict
3: Forcing 0 and X might be a conflict
4: Conflicts propagate: anything and a conflict is a conflict
5: Z is always overridden
?: 1 for pull up, 0 for pull-down
What are the logic families?
Features
- RTL - resistor transistor logic (now obsolete)
- DTL - diode transistor logic (now obsolete)
- TTL - transistor transistor logic (extremely common, becoming less so)
- ECL - emitter coupled logic (fast, heavy on power)
- MOS - metal oxide semiconductor (low power)
- CMOS - complementary metal oxide semiconductor (even less power)
- BiCMOS - Bipolar CMOS (fast, low power, good driving capability)
- GaAs - Gallium Arsenide (very fast)
- SiGe - Silicon Germanium heterojunction (currently fastest)
What is the fastest current logic family?
- Fastest logic made to date:
- SiGe bipolar heterojunction stacked current logic
- Clocks at 80GHz
- fT 450GHz
- Gate delay 6 ps
Flaws of SiGe bipolar heterojunction stacked current logic
•The logic thresholds are different for each input to each gate
Describe Static RAM Cell
● Large (poor packing density)
● Fast
● Power hungry
● Persistent (the data is stable as long as the power is maintained)
Bistable memory.
Describe Dynamic RAM Cell
Holds Bit Value for roughly 1 millisecond
- Highest packing density of all memory topologies
- Three components form the cell
- Two are parasitic
Describe Response of non-inverting amplifier
Ideal, linear increase, however, Output saturates after a certain value as output voltage reaches supply voltage..
Describe the response of inverting analogue amplifier.
Negative Linear. Saturates at high voltage, near supply, and low voltage when close to 0.
The equation for output of inverting analogue amplifier
What happens when we combine two amplifiers back to back
connect them back-to-back so that the input of each is driven by the output of the other, we can superpose the
transfer characteristics, and if the stage gains are high enough, we get the situation shown
in the figure.
What happens if the stage gain when combining the two amplifiers is not high enough?
If the gains are insufficient for the transfer characteristics to intersect like this, we get a
situation where there exists just one stable equilibrium point, at the single crossing point.
(The transition between these two states occurs when the slope of the linear region = 1, i.e.
Rb = βRc)
Define Paging
Paging is a mechanism to separate data and can be used to implement a virtual memory system. It is
architecture-sympathetic ie. architecture side memory management.
Define Segmentation
Segmentation is a memory management mechanism by which data/instructions can be split into segments to divide programs in a user-sympathetic manner.
How are multiple pages implemented?
Page directory is implemented, stores page tables and is never swapped out. It is stored in the OS block.
