Difference between revisions of "Memory"

From Chessprogramming wiki
Jump to: navigation, search
(2 intermediate revisions by the same user not shown)
Line 261: Line 261:
 
* [https://en.wikipedia.org/wiki/Ken_Knowlton Kenneth C. Knowlton] ('''1965'''). ''A Fast storage allocator''. [[ACM#Communications|Communications of the ACM]], Vol. 8, No. 10 : 623-625
 
* [https://en.wikipedia.org/wiki/Ken_Knowlton Kenneth C. Knowlton] ('''1965'''). ''A Fast storage allocator''. [[ACM#Communications|Communications of the ACM]], Vol. 8, No. 10 : 623-625
 
===1970 ...===  
 
===1970 ...===  
 +
* [[Paul W. Purdom]], [[Mathematician#SMStigler|Stephen M. Stigler]] ('''1970'''). ''[https://www.semanticscholar.org/paper/Statistical-Properties-of-the-Buddy-System-Purdom-Stigler/36ffdc1a3960dd9874d676176d1e4bd48c99b528 Statistical Properties of the Buddy System]''. [[ACM#Journal|Journal of the ACM]], Vol. 17, No. 4 <ref>[https://en.wikipedia.org/wiki/Buddy_memory_allocation Buddy memory allocation from Wikipedia]</ref>
 
* [[Donald Eastlake]] ('''1977'''). ''[http://www.informatik.uni-trier.de/~ley/db/conf/vldb/Eastlake77.html Tertiary Memory Access and Performance in the Datacomputer]''. [http://www.informatik.uni-trier.de/~ley/db/conf/vldb/vldb77.html#Eastlake77 VLDB 1977]
 
* [[Donald Eastlake]] ('''1977'''). ''[http://www.informatik.uni-trier.de/~ley/db/conf/vldb/Eastlake77.html Tertiary Memory Access and Performance in the Datacomputer]''. [http://www.informatik.uni-trier.de/~ley/db/conf/vldb/vldb77.html#Eastlake77 VLDB 1977]
 
===1980 ...===  
 
===1980 ...===  
 +
* [[Paul W. Purdom]], [[Mathematician#CABrown|Cynthia A. Brown]] ('''1980'''). ''[https://www.semanticscholar.org/paper/Exact-formulas-for-the-buddy-system-Purdom-Brown/edb813045099fe0e657d20e2c7d5b54ddbb9fbcd Exact formulas for the buddy system]''. [https://en.wikipedia.org/wiki/Information_Sciences_(journal) Information Sciences], Vol. 22, No. 1
 
* [[Ozalp Babaoglu]], [https://en.wikipedia.org/wiki/Bill_Joy William Joy] ('''1981'''). ''Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits''. Proceedings of the 8th SOSP, Operating Systems Review, Vol. 15, No. 5, pp. 78-86
 
* [[Ozalp Babaoglu]], [https://en.wikipedia.org/wiki/Bill_Joy William Joy] ('''1981'''). ''Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits''. Proceedings of the 8th SOSP, Operating Systems Review, Vol. 15, No. 5, pp. 78-86
 
* [[Bruce W. Leverett]], [http://genealogy.math.ndsu.nodak.edu/id.php?id=95738 Peter G. Hibbard] ('''1982'''). ''[http://onlinelibrary.wiley.com/doi/10.1002/spe.4380120606/abstract An Adaptive System for Dynamic Storage Allocation]''. [http://www.informatik.uni-trier.de/~ley/db/journals/spe/spe12.html#LeverettH82 Software: Practice and Experience], [http://onlinelibrary.wiley.com/doi/10.1002/spe.v12:6/issuetoc Vol. 12, No. 6], pp. 543-555
 
* [[Bruce W. Leverett]], [http://genealogy.math.ndsu.nodak.edu/id.php?id=95738 Peter G. Hibbard] ('''1982'''). ''[http://onlinelibrary.wiley.com/doi/10.1002/spe.4380120606/abstract An Adaptive System for Dynamic Storage Allocation]''. [http://www.informatik.uni-trier.de/~ley/db/journals/spe/spe12.html#LeverettH82 Software: Practice and Experience], [http://onlinelibrary.wiley.com/doi/10.1002/spe.v12:6/issuetoc Vol. 12, No. 6], pp. 543-555
Line 270: Line 272:
 
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
 
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
 
* [[Wim Pijls]], [[Arie de Bruin]] ('''1993'''). ''SSS*-like Algorithms in Constrained Memory.'' [[ICGA Journal#16_1|ICCA Journal, Vol. 16, No. 1]]
 
* [[Wim Pijls]], [[Arie de Bruin]] ('''1993'''). ''SSS*-like Algorithms in Constrained Memory.'' [[ICGA Journal#16_1|ICCA Journal, Vol. 16, No. 1]]
* [[Hermann Kaindl]], G. Kainz, A. Leeb, H. Smetana ('''1995'''). ''How to use limited memory in heuristic search''. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), Montreal, Canada, pp. 236-242.
+
* [[Hermann Kaindl]], Gerhard Kainz, Angelika Leeb, Harald Smetana ('''1995'''). ''How to use limited memory in heuristic search''. [[Conferences#IJCAI1995|IJCAI 1995]]
 
* [[Matteo Frigo]] ('''1997'''). ''The weakest reasonable memory model.'' Masters Thesis, [[Massachusetts Institute of Technology]], Department of Electrical Engineering and Computer Science, [http://supertech.csail.mit.edu/papers/frigo-ms-thesis.pdf pdf]
 
* [[Matteo Frigo]] ('''1997'''). ''The weakest reasonable memory model.'' Masters Thesis, [[Massachusetts Institute of Technology]], Department of Electrical Engineering and Computer Science, [http://supertech.csail.mit.edu/papers/frigo-ms-thesis.pdf pdf]
 
* [[Dennis Breuker]] ('''1998'''). ''Memory versus Search in Games''. Ph.D. thesis, [[Maastricht University]], pdf available via [http://www.dennisbreuker.nl/thesis/index.html Dennis Breuker's page]
 
* [[Dennis Breuker]] ('''1998'''). ''Memory versus Search in Games''. Ph.D. thesis, [[Maastricht University]], pdf available via [http://www.dennisbreuker.nl/thesis/index.html Dennis Breuker's page]
Line 310: Line 312:
 
===1980 ...===  
 
===1980 ...===  
 
* [[Marvin Minsky]] ('''1980'''). ''K-Lines: A Theory of Memory''. Cognitive Science 4, 117-133, [http://csjarchive.cogsci.rpi.edu/1980v04/i02/p0117p0133/MAIN.PDF pdf] <ref>[https://en.wikipedia.org/wiki/K-line_%28artificial_intelligence%29 K-line (artificial intelligence) from Wikipedia]</ref>
 
* [[Marvin Minsky]] ('''1980'''). ''K-Lines: A Theory of Memory''. Cognitive Science 4, 117-133, [http://csjarchive.cogsci.rpi.edu/1980v04/i02/p0117p0133/MAIN.PDF pdf] <ref>[https://en.wikipedia.org/wiki/K-line_%28artificial_intelligence%29 K-line (artificial intelligence) from Wikipedia]</ref>
* [[Dennis H. Holding]], [[Robert I. Reynolds]] ('''1982'''). ''[http://link.springer.com/article/10.3758%2FBF03197635?LI=true#page-1 Recall or Evaluation of Chess Positions as Determinants of Chess Skill]''. [http://www.springer.com/psychology/cognitive+psychology/journal/13421 Memory & Cognition], Vol. 10, No. 3, 237-242
+
* [[Dennis H. Holding]], [[Robert I. Reynolds]] ('''1982'''). ''[https://link.springer.com/article/10.3758/BF03197635 Recall or Evaluation of Chess Positions as Determinants of Chess Skill]''. [https://www.springer.com/journal/13421 Memory & Cognition], Vol. 10, No. 3
 
* [[A. Harry Klopf]] ('''1982'''). ''The Hedonistic Neuron: A Theory of Memory, Learning, and Intelligence''. Hemisphere Publishing Corporation, [[University of Michigan]]
 
* [[A. Harry Klopf]] ('''1982'''). ''The Hedonistic Neuron: A Theory of Memory, Learning, and Intelligence''. Hemisphere Publishing Corporation, [[University of Michigan]]
 
===1990 ...===  
 
===1990 ...===  
Line 385: Line 387:
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74751 History of Memory Wall in Computer Chess?] by [[Srdja Matovic]], [[CCC]], August 11, 2020
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74751 History of Memory Wall in Computer Chess?] by [[Srdja Matovic]], [[CCC]], August 11, 2020
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75116 Memory management and threads] by [[Chris Whittington]], [[CCC]], September 15, 2020 » [[Thread]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75116 Memory management and threads] by [[Chris Whittington]], [[CCC]], September 15, 2020 » [[Thread]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77054 PERFT transposition table funny?!] by [[Martin Bryant]], [[CCC]], April 10, 2021 » [[Perft]], [[Transposition Table]]
  
 
=External Links=  
 
=External Links=  

Revision as of 15:20, 10 April 2021

Home * Hardware * Memory

RNA, biological data storage [1]

Memory is the ability to store, retain, and recall information and experiences as researched in cognitive science. Computer memory refers to physical devices used to store data and sequences of instructions (programs) on a temporary or permanent basis, typically distinguished as fast random-access memory and relatively slow data storage.

Flip-Flop

A flip-flop or latch is a one bit memory. For instance a simple relay (K1) with its contact parallel to the On-push-button S2, "remembers" whether last action was pushing S1 (reset) or S2 (set) [2] .

Selbsthaltung.gif

A RS flip-flop is a pair of cross-coupled NAND or NOR-gates, where the outputs are feed back to the inputs. A D flip-flop, the most common flip-flop, stores the input D with the rising edge (0-1 transition) of a clock.

RS flip-flop D flip-flop Discrete
RS flipflop.svg
D-Type Flip-flop.svg
Flipflop6as.jpg
R-S mk2.gif
Edge triggered D flip flop.svg
from two NOR (red == 1) [3] from six NAND [4] PDP-6 flip-flop [5] [6]

N-Bit Latches

N-Bit latches are arrays of one-bit latches or flip-flops typically as wide as a connected parallel data-bus. They may be used as a registers or scratchpad RAM inside a central processing unit.

RAM

Random access memory is a fast form of computer memory and refers to the idea that any piece of data can be stored and retrieved in a constant time, regardless of its physical location and whether or not it is related to the previous piece of data.

Static RAM

Static RAM (SRAM) is an array of latches, where each latch has a unique address, which connects the addressed latch to its data-bus, often used as CPU cache.

Dynamic RAM

Dynamic random access memory (DRAM) is a type of random access memory that stores each bit of data in a separate capacitor within an electronic circuit. Since capacitors leak charge, the information eventually fades unless the capacitor charge is refreshed periodically, which is the reason to call that memory dynamic. Since DRAM takes only one transistor and capacitor per bit, it is therefor used as cheap main memory part of recent computer data storage, despite its worse latency compared to SRAM.

Square array of mosfet cells read.png

DRAM write at a 4 by 4 array [7]

ROM

Read-only memory (ROM) is a class of storage programmed once and mainly used to distribute firmware. EPROMs have a small quartz window which admits UV light for erasure [8] . ROM or EPROM were often embedded inside a microcontroller in conjunction with some RAM. They were often used in dedicated chess computers.

EPROMs National Semiconductor.jpg

National Semiconductor EPROMs 2764 and 2716 [9]

Since each data-bit stored in a ROM is a boolean function of its inputs or address, a ROM is also used to implement combinatorial logic.

Persistence

Auxiliary Storage

Beside the computer's random access main memory, auxiliary storage refer to mass storage like optical discs, and magnetic storage hard disk drives. Those devices are usually connected via a serial bus, and accessed via streams.

Intelligent Chess 1 20x20.JPG

Compact Cassette as Auxiliary Storage in Intelligent Chess [10]

USB 3.0

Historical Data Storage

Coincident-current magnetic core.svg
Plated wire memory from Wikipedia
Pamiec bebnowa 1.jpg

Memory Hierarchy

ComputerMemoryHierarchy.svg

Memory Management

Todays processors utilize all the above types of memory from small and fast to large but slow within the concepts of virtual memory, paging, protection and various caches.

Virtual Memory

Page table actions.svg
Virtual address space and physical address space relationship.svg
Physical address translation [12] Virtual and physical address space [13]

Paging

Page table
Page replacement algorithm
Paging
Demand Paging
Page fault
Copy-on-write

TLB

Huge Pages

Note that what Windows calls "large pages," Linux and Unix call "huge pages" or "huge TLB pages (x86 and x86-64)

Memory Model

Shared Memory

Shared Memory:

False sharing from Wikipedia

Cache

Cache:

MSI protocol from Wikipedia
MESI protocol from Wikipedia
MOESI protocol from Wikipedia
assembly - The prefetch instruction - Stack Overflow
Data Prefetch Support - GNU Project - Free Software Foundation (FSF)
Software prefetching considered harmful by Linus Torvalds, LWN.net, May 19, 2011

Segmentation

Allocation

Manual memory management
Memory leak
Garbage collection

Memory Footprint

Beside their individual memory footprint, chess programs have to deal with huge memory areas of transposition table and possibly caches for endgame table- or bitbases and their relative huge random access latencies.

Miles Davis, Wayne Shorter, Herbie Hancock, Ron Carter, Tony Williams
Monika Malczak, Mateusz Gramburg, Paweł Zwierzyński-Pióro, Michał Szeligowski

Multiprocessing

Memory versus Search

See also

Publications

Computer Memory

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

Memory part 1
Memory part 2: CPU caches
Memory part 3: Virtual Memory
Memory part 4: NUMA support
Memory part 5: What programmers can do

2010 ...

Cognition

1960 ...

  • Adriaan de Groot (1966). Perception and Memory versus Thought: Some Old Ideas and Recent Findings. Problem Solving: Research, Method, and Theory (ed. B. Kleinmuntz), pp. 19-50. John Wiley, New York.

1970 ...

1980 ...

1990 ...

2000 ...

Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017 ...

2020 ...

External Links

Computer Memory

Gustavo Duarte's Blog

from Best Of by Gustavo Duarte:

Cognition

Neuroscience

Misc

References

Up one Level