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 if 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
A think tank is an organization that presents ideas presented as expert analysis. Most think tank reports is presented as the product of specialists that are not pure consultants, for which all work is billable, but who have time to research, study, and think. This is not to say that consulting firms may not produce excellent work, but their business model is, much as is a law firm, that their professional staff time is billable to a specific client.
While some do experimentation, research laboratories, regardless of sponsorship, are usually not considered think tanks, which focus on the thinking, not the doing.
Think tanks vary widely in the independence of their work. Many are little more than public relations fronts for a particular ideology or interest group, while others have a reputation for balance. Several reports put the Brookings Institution as among the most neutral and most frequently cited think tank. [1], and closest to the ideological center of similar organizations. [2] Other think tanks considered largely independent include the Center for Strategic and International Studies and Council on Foreign Relations.
Many think tanks were created, by the U.S. government, at the end of the Second World War, for providing analysis either independent of government bias, or to use specialists who, for reasons ranging from salary to working conditions, did not want to work directly for government. The best known of these is the RAND Corporation, established by the United States Air Force. RAND and others, such as the MITRE Corporation and its MITREtek subsidiary, have diversified and are not solely dependent on government funding. Others, such as the Institute for Defense Analyses, restrict their contracts to government work, often highly classified. A number of think tanks -- including MITRE and IDA -- have chosen to operate as "Federally Funded Research and Development Centers (FFRDCs)", an operational mode which provides special non-competitive status under the provisions of the Federal Acquisition Regulation (FAR) and other Federal procurement, taxation, and acquisition regulations.
Over time, governments have found it useful to create internal think tanks with substantial independence, such as the Strategic Studies Institute of the U.S. Army War College.
In the private sector, a number of think tanks, such as the American Enterprise Institute or American Civil Liberties Union, have a stated ideological position, but may do substantive work within those assumptions. Groseclose and Milyo found that indicators of centrism were
- the organization had closed membership (i.e., one could not simply join if sympathetic)
- staff had titles such as fellow (including research fellow or senior fellow), researcher, economist, or analyst. (Read more...)
|
