Article of the Week about
Locality of reference is a commonly observed pattern in memory accesses by a computer program over time. The idea is, that memory accesses that happen close to one another in time tend to occur close to one another in space (memory address). Locality of reference is one of the primary motivations for copying data in chunks from slower memory to faster memory in the memory hierarchy. Examples are memory caches, which attempt to load a range of main memory contents at a time, and memory paging where pages of 1024 bytes or more are stored on and retrieved from harddisks in one go. Each time the assumption is made that the excess memory contents will be needed soon after.
Locality of reference can be exploited by a computer's memory controller for drastic improvements in memory access times. In general, whenever a memory access takes place, the memory controller will attempt to read a larger section of memory which contains the target address. In the common case, subsequent memory accesses will likely target memory addresses that have been loaded into the cache by that same read.
Thought experiment: fetch-execute cycle
When a typical computer is executing a program, it repeatedly reads the next instruction in memory and then executes it. Typically, those instructions are placed in sequential memory addresses, with exceptions for branches that occur for control structures such as loops, conditionals and function or method invocations.
Thought experiment: array algorithms
Suppose we had an algorithm which was to select the largest number in an array. One straight-forward way to accomplish this (indeed, the optimal solution for an unsorted flat array) is to iterate over each element of the array in order, and check whether each one is the largest so far. Thus, at time T=0, we check element 0, at T=1, we check element 1, and so on. Without a cache, the processor would need to spend a little bit of time during each instruction cycle to fetch the array element from main memory. But, if the processor employs a cache, we can achieve a speed-up as follows.
Once the algorithm attempts its first read, the processor's memory controller will fetch not just that element, but the entire cache line which contains that element. The processor must wait for that element before it can proceed, but the memory controller can continue fetching the rest while the processor moves on to the next instruction. As a result, for the next few elements we can avoid a memory stall with each array access. (Read more...)
|
New Draft of the Week about
Racism in Australia
Australia has a long history of racism dating back to the founding of the first colony in Sydney Cove. The establishment of the British colony in 1788 was justified by a racist ideology later expressed by the 'Terra Nullius' concept, in which the colonists believed they had first rights to the land over other groups. Racism is closely tied to nationalism, and the use of immigrants as scapegoats during lean economic times.
Lambing Flat massacre
Australia's experience with the Chinese on the goldfields probably established the pattern of discriminatory practice towards Chinese in particular and Asians in general. Early Asian immigrants in Australia generally took jobs unwanted by Europeans such as railway workers, shepherds on new land, fruit pickers and clearing bushland. By the early 19th century, with 24,000 Chinese immigrants in Australia there was a perception about Australia being 'overrun'. More particularly, Chinese miners were a perceived threat to the Australian economy. The discovery of gold in Australia and a subsequent Gold Rush saw a boom of Asian immigrants against extreme difficulties posed by white settlers such as the Poll Taxes of ten pounds in Victorian ports and widespread anti-Chinese violence. (Read more...)
|
