:: wikimiki.org ::

Computer

Computer

A computer is a device capable of processing data according to a program — a list of instructions. The data to be processed may represent many types of information including numbers, text, pictures, or sound. Computers can be extremely versatile. In fact, they are universal information processing machines. According to the Church-Turing thesis, a computer with a certain minimum threshold capability is in principle capable of performing the tasks of any other computer, from those of a personal digital assistant to a supercomputer. Therefore, the same computer designs have been adapted for tasks from processing company payrolls to controlling industrial robots. Modern electronic computers also have enormous speed and capacity for information processing compared to earlier designs, and they have become exponentially more powerful over the years (a phenomenon known as Moore's Law). Computers are available in many physical forms. The original computers were the size of a large room, and such enormous computing facilities still exist for specialized scientific computation - supercomputers - and for the transaction processing requirements of large companies, generally called mainframes. Smaller computers for individual use, called personal computers, and their portable equivalent, the notebook computer, are ubiquitous information-processing and communication tools and are perhaps what most non-experts think of as "a computer". However, the most common form of computer in use today is the embedded computer, small computers used to control another device. Embedded computers control machines from fighter planes to digital cameras.

History of computing

Originally, a "computer" was a person who performed numerical calculations under the direction of a mathematician, often with the aid of a variety of mechanical calculating devices from the abacus onward. An example of an early computing device was the Antikythera mechanism, an ancient Greek device for calculating the movements of planets, dating from about 87 BCE. The technology responsible for this mysterious device seems to have been lost at some point. The end of the Middle Ages saw a reinvigoration of European mathematics and engineering, and by the early 17th century a succession of mechanical calculating devices had been constructed using clockwork technology. A considerable number of technologies that would later prove vital for the digital computer were developed in the late 19th and early 20th centuries, such as the punched card and the vacuum tube ((or valve). Charles Babbage was the first to conceptualize and design a fully programmable computer as early as 1837, but due to a combination of the limits of the technology of the time, limited finance, and an inability to resist tinkering with his design (a trait that would in time doom thousands of computer-related engineering projects), the device was never actually constructed in his lifetime. During the first half of the 20th century, many scientific computing needs were met by increasingly sophisticated, special-purpose analog computers, which used a direct physical or electrical model of the problem as a basis for computation. These became increasingly rare after the development of the digital computer. A succession of steadily more powerful and flexible computing devices were constructed in the 1930s and 1940s, gradually adding the key features of modern computers, such as the use of digital electronics (invented by Claude Shannon in 1937) and more flexible programmability. Defining one point along this road as "the first computer" is exceedingly difficult. Notable achievements include the Atanasoff Berry Computer, a special-purpose machine that used valve-driven computation and binary numbers; Konrad Zuse's Z machines; the secret British Colossus computer, which had limited programmability but demonstrated that a device using thousands of valves could be made reliable and reprogrammed electronically; and the American ENIAC — the first general purpose machine, but with an inflexible architecture that meant reprogramming it essentially required it to be rewired. The team who developed ENIAC, recognizing its flaws, came up with a far more flexible and elegant design, which has become known as the stored program architecture, which is the basis from which virtually all modern computers were derived. A number of projects to develop computers based on the stored program architecture commenced in the late 1940s; the first of these to be up and running was the Small-Scale Experimental Machine, but the EDSAC was perhaps the first practical version. Valve-driven computer designs were in use throughout the 1950s, but were eventually replaced with transistor-based computers, which were smaller, faster, cheaper, and much more reliable, thus allowing them to be commercially produced, in the 1960s. By the 1970s, the adoption of integrated circuit technology had enabled computers to be produced at a low enough cost to allow individuals to own a personal computer of the type familiar today.

How computers work: the stored program architecture

While the technologies used in computers have changed dramatically since the first electronic, general-purpose, computers of the 1940s, most still use the stored program architecture (sometimes called the von Neumann architecture; as the article describes the primary inventors were probably ENIAC designers J. Presper Eckert and John William Mauchly). The design made the universal computer a practical reality. The architecture describes a computer with four main sections: the arithmetic and logic unit (ALU), the control circuitry, the memory, and the input and output devices (collectively termed I/O). These parts are interconnected by a bundle of wires (a "bus") and are usually driven by a timer or clock (although other events could drive the control circuitry). Conceptually, a computer's memory can be viewed as a list of cells. Each cell has a numbered "address" and can store a small, fixed amount of information. This information can either be an instruction, telling the computer what to do, or data, the information which the computer is to process using the instructions that have been placed in the memory. In principle, any cell can be used to store either instructions or data. The ALU is in many senses the heart of the computer. It is capable of performing two classes of basic operations: arithmetic operations, the core of which is the ability to add or subtract two numbers but also encompasses operations like "multiply this number by 2" or "divide by 2" (for reasons which will become clear later), as well as some others. The second class of ALU operations involves comparison operations, which, given two numbers, can determine if they are equal, and if not, which is bigger. The I/O systems are the means by which the computer receives information from the outside world, and reports its results back to that world. On a typical personal computer, input devices include objects like the keyboard and mouse, and output devices include computer monitors, printers and the like, but as will be discussed later a huge variety of devices can be connected to a computer and serve as I/O devices. The control system ties this all together. Its job is to read instructions and data from memory or the I/O devices, decode the instructions, providing the ALU with the correct inputs according to the instructions, "tell" the ALU what operation to perform on those inputs, and send the results back to the memory or to the I/O devices. One key component of the control system is a counter that keeps track of what the address of the current instruction is; typically, this is incremented each time an instruction is executed, unless the instruction itself indicates that the next instruction should be at some other location (allowing the computer to repeatedly execute the same instructions). Physically, since the 1980s the ALU and control unit have been located on a single integrated circuit called a Central Processing Unit or CPU. The functioning of such a computer is in principle quite straightforward. Typically, on each clock cycle, the computer fetches instructions and data from its memory. The instructions are executed, the results are stored, and the next instruction is fetched. This procedure repeats until a halt instruction is encountered. Larger computers, such as some minicomputers, mainframe computers, servers, differ from the model above in one significant aspect; rather than one CPU they often have a number of them. Supercomputers often have highly unusual architectures significantly different from the basic stored-program architecture, sometimes featuring thousands of CPUs, but such designs tend to be useful only for specialized tasks.

Digital circuits

The conceptual design above could be implemented using a variety of different technologies. As previously mentioned, a stored program computer could be designed entirely of mechanical components like Babbage's. However, digital circuits allow Boolean logic and arithmetic using binary numerals to be implemented using relays - essentially, electrically controlled switches. Shannon's famous thesis showed how relays could be arranged to form units called logic gates, implementing simple Boolean operations. Others soon figured out that vacuum tubes - electronic devices, could be used instead. Vacuum tubes were originally used as a signal amplifier for radio and other applications, but were used in digital electronics as a very fast switch; when electricity is provided to one of the pins, current can flow through between the other two. Through arrangements of logic gates, one can build digital circuits to do more complex tasks, for instance, an adder, which implements in electronics the same method - in computer terminology, an algorithm - to add two numbers together that children are taught - add one column at a time, and carry what's left over. Eventually, through combining circuits together, a complete ALU and control system can be built up. This does require a considerable number of components. CSIRAC, one of the earliest stored-program computers, is probably close to the smallest practically useful design. It had about 2,000 valves, some of which were "dual components", so this represented somewhere between 2 and 4,000 logic components. Vacuum tubes had severe limitations for the construction of large numbers of gates. They were expensive, unreliable (particularly when used in such large quantities), took up a lot of space, and used a lot of electrical power, and, while incredibly fast compared to a mechanical switch, had limits to the speed at which they could operate. Therefore, by the 1960s they were replaced by the transistor, a new device which performed the same task as the tube but was much smaller, faster operating, reliable, used much less power, and was far cheaper. transistor In the 1960s and 1970s, the transistor itself was gradually replaced by the integrated circuit, which placed multiple transistors (and other components) and the wires connecting them on a single, solid piece of silicon. By the 1970s, the entire ALU and control unit, the combination becoming known as a CPU, were being placed on a single "chip" called a microprocessor. Over the history of the integrated circuit, the number of components that can be placed on one has grown enormously. The first IC's contained a few tens of components; as of 2005, modern microprocessors such from AMD and Intel contain over 100 million transistors. Tubes, transistors, and transistors on integrated circuits can be and are used as the "storage" component of the stored-program architecture, using a circuit design known as a flip-flop, and indeed flip-flops are used for small amounts of very high-speed storage. However, few computer designs have used flip-flops for the bulk of their storage needs. Instead, earliest computers stored data in Williams tubes - essentially, projecting some dots on a TV screen and reading them again, or mercury delay lines where the data was stored as sound pulses traveling slowly (compared to the machine itself) along long tubes filled with mercury. These somewhat ungainly but effective methods were eventually replaced by magnetic memory devices, such as magnetic core memory, where electrical currents were used to introduce a permanent (but weak) magnetic field in some ferrous material, which could then be read to retrieve the data. Eventually, DRAM was introduced. A DRAM unit is a type of integrated circuit containing huge banks of an electronic component called a capacitor which can store an electrical charge for a period of time. The level of charge in a capacitor could be set to store information, and then measured to read the information when required.

I/O devices

I/O is a general term for devices that send computers information from the outside world and that return the results of computations. These results can either be viewed directly by a user, or they can be sent to another machine, whose control has been assigned the computer: In a robot, for instance, the controlling computer's major output device is the robot itself. The first generation of computers were equipped with a fairly limited range of input devices. A punch card reader, or something similar, was used to enter instructions and data into the computer's memory, and some kind of printer, usually a modified teletype, was used to record the results. Over the years, a huge variety of other devices have been added. For the personal computer, for instance, keyboards and mice are the primary ways people directly enter information into the computer; and monitors are the primary way in which information from the computer is presented back to the user, though printers, speakers, and headphones are common, too. There is a huge variety of other devices for obtaining other types of input. One example is the digital camera, which can be used to input visual information. There are two prominent classes of I/O devices. The first class is that of secondary storage devices, such as hard disks, CD-ROMs, key drives and the like, which represent comparatively slow, but high-capacity devices, where information can be stored for later retrieval; the second class is that of devices used to access computer networks. The ability to transfer data between computers has opened up a huge range of capabilities for the computer. The global Internet allows millions of computers to transfer information of all types between each other.

Instructions

The instructions interpreted by the control unit, and executed by the ALU, are not nearly as rich as a human language. A computer responds only to a limited number of instructions, but they are well defined, simple, and unambiguous. Typical sorts of instructions supported by most computers are "copy the contents of memory cell 5 and place the copy in cell 10", "add the contents of cell 7 to the contents of cell 13 and place the result in cell 20", "if the contents of cell 999 are 0, the next instruction is at cell 30". All computer instructions fall into one of four categories: 1) moving data from one location to another; 2) executing arithmetic and logical processes on data; 3) testing the condition of data; and 4) altering the sequence of operations. Instructions are represented within the computer as binary code - a base two system of counting. For example, the code for one kind of "copy" operation in the Intel line of microprocessors is 10110000. The particular instruction set that a specific computer supports is known as that computer's machine language. To slightly oversimplify, if two computers have CPUs that respond to the same set of instructions identically, software from one can run on the other without modification. This easy portability of existing software creates a great incentive to stick with existing designs, only switching for the most compelling of reasons, and has gradually narrowed the number of distinct instruction set architectures in the marketplace.

Programs

Computer programs are simply lists of instructions for the computer to execute. These can range from just a few instructions which perform a simple task, to a much more complex instruction list which may also include tables of data. Many computer programs contain millions of instructions, and many of those instructions are executed repeatedly. A typical modern PC (in the year 2005) can execute around 3 billion instructions per second. Computers do not gain their extraordinary capabilities through the ability to execute complex instructions. Rather, they do millions of simple instructions arranged by people known as programmers. In practice, people do not normally write the instructions for computers directly in machine language. Such programming is incredibly tedious and highly error-prone, making programmers very unproductive. Instead, programmers describe the desired actions in a "high level" programming language which is then translated into the machine language automatically by special computer programs (interpreters and compilers). Some programming languages map very closely to the machine language, such as Assembly Language (low level languages); at the other end, languages like Prolog are based on abstract principles far removed from the details of the machine's actual operation (high level languages). The language chosen for a particular task depends on the nature of the task, the skill set of the programmers, tool availability and, often, the requirements of the customers (for instance, projects for the US military were often required to be in the Ada programming language). Computer software is an alternative term for computer programs; it is a more inclusive phrase and includes all the ancillary material accompanying the program needed to do useful tasks. For instance, a video game includes not only the program itself, but also data representing the pictures, sounds, and other material needed to create the virtual environment of the game. A computer application is a piece of computer software provided to many computer users, often in a retail environment. The stereotypical modern example of an application is perhaps the office suite, a set of interrelated programs for performing common office tasks. Going from the extremely simple capabilities of a single machine language instruction to the myriad capabilities of application programs means that many computer programs are extremely large and complex. A typical example is the Firefox web browser, created from roughly 2 million lines of computer code in the C++ programming language; there are many projects of even bigger scope, built by large teams of programmers. The management of this enormous complexity is key to making such projects possible; programming languages, and programming practices, enable the task to be divided into smaller and smaller subtasks until they come within the capabilities of a single programmer in a reasonable period. Nevertheless, the process of developing software remains slow, unpredictable, and error-prone; the discipline of software engineering has attempted, with some partial success, to make the process quicker and more productive and improve the quality of the end product.

Libraries and operating systems

Soon after the development of the computer, it was discovered that certain tasks were required in many different programs; an early example was computing some of the standard mathematical functions. For the purposes of efficiency, standard versions of these were collected in libraries and made available to all who required them. A particularly common task set related to handling the gritty details of "talking" to the various I/O devices, so libraries for these were quickly developed. By the 1960s, with computers in wide industrial use for many purposes, it became common for them to be used for many different jobs within an organization. Soon, special software to automate the scheduling and execution of these many jobs became available. The combination of managing "hardware" and scheduling jobs became known as the "operating system"; the classic example of this type of early operating system was OS/360 by IBM. The next major development in operating systems was timesharing - the idea that multiple users could use the machine "simultaneously" by keeping all of their programs in memory, executing each user's program for a short time so as to provide the illusion that each user had their own computer. Such a development required the operating system to provide each user's programs with a "virtual machine" such that one user's program could not interfere with another's (by accident or design). The range of devices that operating systems had to manage also expanded; a notable one was hard disks; the idea of individual "files" and a hierarchical structure of "directories" (now often called folders) greatly simplified the use of these devices for permanent storage. Security access controls, allowing computer users access only to files, directories and programs they had permissions to use, were also common. Perhaps the last major addition to the operating system were tools to provide programs with a standardized graphical user interface. While there are few technical reasons why a GUI has to be tied to the rest of an operating system, it allows the operating system vendor to encourage all the software for their operating system to have a similar looking and acting interface. Outside these "core" functions, operating systems are usually shipped with an array of other tools, some of which may have little connection with these original core functions but have been found useful by enough customers for a provider to include them. For instance, Apple's Mac OS X ships with a digital video editor application. Not all operating systems provide all of the above functions; operating systems for smaller computers typically provide fewer, such as the highly minimal operating systems for early microcomputers. Embedded computers may have a specialized operating system, or sometimes none at all. Instead, the custom programs written for their task perform all necessary functions that would be performed by an operating system in less specialized roles.

Computer applications

Embedded computer The first electronic digital computers, with their large size and cost, mainly performed scientific calculations, often to support military objectives. The ENIAC was originally designed to calculate ballistics-firing tables for artillery, but it was also used to calculate neutron cross-sectional densities to help in the design of the hydrogen bomb. This calculation, performed in December, 1945 through January, 1946 and involving over a million punch cards of data, showed the design then under consideration would fail. (Many of the most powerful supercomputers available today are also used for nuclear weapons simulations.) The CSIR Mk I, the first Australian stored-program computer, evaluated rainfall patterns for the catchment area of the Snowy Mountains Scheme, a large hydroelectric generation project. Others were used in cryptanalysis, for example the first programmable (though not general-purpose) digital electronic computer, Colossus, built in 1943 during World War II. Despite this early focus of scientific and military engineering applications, computers were quickly used in other areas. From the beginning, stored program computers were applied to business problems. The LEO, a stored program-computer built by J. Lyons and Co. in the United Kingdom, was operational and being used for inventory management and other purposes 3 years before IBM built their first commercial stored-program computer. Continual reductions in the cost and size of computers saw them adopted by ever-smaller organizations. Moreover, with the invention of the microprocessor in the 1970s, it became possible to produce inexpensive computers. In the 1980s, personal computers became popular for many tasks, including book-keeping, writing and printing documents, calculating forecasts and other repetitive mathematical tasks involving spreadsheets. spreadsheet (1989) marked the acceptance of CGI in the visual effects industry.]] As computers have become cheaper, they have been used extensively in the creative arts as well. Sound, still pictures, and video are now routinely created (through synthesizers, computer graphics and computer animation), and near-universally edited by computer. They have also been used for entertainment, with the video game becoming a huge industry. Computers have been used to control mechanical devices since they became small and cheap enough to do so; indeed, a major spur for integrated circuit technology was building a computer small enough to guide the Apollo missions and the Minuteman missile, two of the first major applications for embedded computers. Today, it is almost rarer to find a powered mechanical device not controlled by a computer than to find one that is at least partly so. Perhaps the most famous computer-controlled mechanical devices are robots, machines with more-or-less human appearance and some subset of their capabilities. Industrial robots have become commonplace in mass production, but general-purpose human-like robots have not lived up to the promise of their fictional counterparts and remain either toys or research projects. Robotics, indeed, is the physical expressions of the field of artificial intelligence, a discipline whose exact boundaries are fuzzy but to some degree involves attempting to give computers capabilities that they do not currently possess but humans do. Over the years, methods have been developed to allow computers to do things previously regarded as the exclusive domain of humans - for instance, "read" handwriting, play chess, or perform symbolic integration. However, progress on creating a computer that exhibits "general" intelligence comparable to a human has been extremely slow.

Networking and the Internet

In the 1970s, computer engineers at research institutions throughout the US began to link their computers together using telecommunications technology. This effort was funded by ARPA, and the computer network that it produced was called the ARPANET. The technologies that made the Arpanet possible spread and evolved. In time, the network spread beyond academic and military institutions and became known as the Internet. The emergence of networking involved a redefinition of the nature and boundaries of the computer. In the phrase of John Gage and Bill Joy (of Sun Microsystems), "the network is the computer". Computer operating systems and applications were modified to include the ability to define and access the resources of other computers on the network, such as peripheral devices, stored information, and the like, as extensions of the resources of an individual computer. Initially these facilities were available primarily to people working in high-tech environments, but in the 1990s the spread of applications like email and the World Wide Web, combined with the development of cheap, fast networking technologies like Ethernet and ADSL saw computer networking become ubiquitous almost everywhere. In fact, the number of computers that are networked is growing phenomenally. A very large proportion of personal computers regularly connect to the Internet to communicate and receive information.

Computing professions and disciplines

In the developed world, virtually every profession makes use of computers. However, certain professional and academic disciplines have evolved that specialize in techniques to construct, program, and use computers. Terminology for different professional disciplines is still somewhat fluid and new fields emerge from time to time: however, some of the major groupings are as follows:
- Computer engineering is that branch of electronic engineering devoted to the physical construction of computers and their attendant components.
- Computer science is an academic study of the processes related to computation, such as developing efficient algorithms to perform specific tasks. It has tackled questions as to whether problems can be solved at all using a computer, how efficiently they can be solved, and how to construct efficient programs to compute solutions. A huge array of specialties has developed within computer science to investigate different classes of problem.
- Software engineering concentrates on methodologies and practices to allow the development of reliable software systems while minimizing, and reliably estimating, costs and timelines.
- Information systems concentrates on the use and deployment of computer systems in a wider organizational (usually business) context.
- Many disciplines have developed at the intersection of computers with other professions; one of many examples is experts in geographical information systems who apply computer technology to problems of managing geographical information.

References

- [http://www.andrew.mallett.net/tech Learn to configure your computer at Andy's Tech Page] category: computer science ja:コンピュータ ko:컴퓨터 ms:Komputer nb:Datamaskin simple:Computer th:คอมพิวเตอร์

Data

Data is the plural of datum. A datum is a statement accepted at face value (a "given"). A large class of practically important statements are measurements or observations of a variable. Such statements may comprise numbers, words, or images.

Etymology

The word data is the plural of Latin datum, neuter past participle of dare, "to give", hence "something given". The past participle of "to give" has been used for millennia, in the sense of a statement accepted at face value; one of the works of Euclid, circa 300 BC, was the Dedomena (in Latin, Data). In discussions of problems in geometry, mathematics, engineering, and so on, the terms givens and data are used interchangeably. Such usage is the origin of data as a concept in computer science: data are numbers, words, images, etc., accepted as they stand.

Usage in English

In English, the word datum is still used in the general sense of "something given", and more specifically in cartography, geography, geology, and drafting to mean a reference point, reference line, or reference surface. The Latin plural data is also used as a plural in English, but it is also commonly treated as a mass noun and used in the singular. For example, "This is all the data from the experiment". This usage is inconsistent with the rules of Latin grammar, which would suggest, "These are the data ...” each measurement or result is a single datum. However, given the variety and irregularity of English plural constructions, there seem to be no grounds for arguing that data is incorrect as a singular mass noun in English.

Uses of data in computing

Raw data are numbers, characters, images or other outputs from devices to convert physical quantities into symbols, in a very broad sense. Such data are typically further processed by a human or input into a computer, stored and processed there, or transmitted (output) to another human or computer. Raw data is a relative term; data processing commonly occurs by stages, and the "processed data" from one stage may be considered the "raw data" of the next. Mechanical computing devices are classified according to the means by which they represent data. An analog computer represents a datum as a voltage, distance, position, or other physical quantity. A digital computer represents a datum as a sequence of symbols drawn from a fixed alphabet. The most common digital computers use a binary alphabet, that is, an alphabet of two characters, typically denoted "0" and "1". More familiar representations, such as numbers or letters, are then constructed from the binary alphabet. Some special forms of data are distinguished. A computer program is a collection of data, which can be interpreted as instructions. Most computer languages make a distinction between programs and the other data on which programs operate, but in some languages, notably Lisp and similar languages, programs are essentially indistinguishable from other data. It is also useful to distinguish metadata, that is, a description of other data. The prototypical example of metadata is the library catalog, which is a description of the contents of books.

Meaning of data, information and knowledge

The terms information and knowledge are frequently used for the concept. These three concepts are ill defined in the subject matter literature. In the recent interdisciplinary research a few independent specializations of these terms are proposed.

References

Category:Data_management Category:Computer_data ko:데이터 ja:データ simple:Data

Church-Turing Thesis

In computability theory the Church–Turing thesis, Church's thesis, Church's conjecture or Turing's thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. The thesis claims that any calculation that is possible can be performed by an algorithm running on a computer, provided that sufficient time and storage space are available. It is generally assumed that an algorithm must satisfy the following requirements: #The algorithm consists of a finite set of simple and precise instructions that are described with a finite number of symbols. #The algorithm will always produce the result in a finite number of steps. #The algorithm can in principle be carried out by a human being with only paper and pencil. #The execution of the algorithm requires no intelligence of the human being except that which is needed to understand and execute the instructions. The Euclidean algorithm for determining the greatest common divisor of two natural numbers is an example of such an algorithm. This description of algorithm is intuitively clear but lacks formal rigor, since it is not exactly clear what a "simple and precise instruction" is, and what exactly the "required intelligence to execute these instructions" is. (See, for example, effective results in number theory for cases well beyond the Euclidean algorithm.) Informally the thesis states that our notion of algorithm can be made precise (in the form of computable functions) and computers can run those algorithms. Furthermore, a computer can theoretically run any algorithm; that is, all ordinary computers (read: Turing machine) are equivalent to each other in terms of theoretical computational power, and it is not possible to build a calculation device that is more powerful than a computer. (Note that this formulation of power disregards practical factors such as speed or memory capacity; it considers all that is theoretically possible, given unlimited time and memory.) The thesis may be regarded as a physical law as it cannot be mathematically proven.

Church–Turing thesis

The thesis, in Turing's own words, can be stated as: :"Every 'function which would naturally be regarded as computable' can be computed by a Turing machine." Due to the vagueness of the concept of a "function which would naturally be regarded as computable", the thesis cannot formally be proven. Disproof would be possible only if humanity found ways of building hypercomputers whose results should "naturally be regarded as computable". Any computer program can be translated into a Turing machine, and any Turing machine can be translated into any general-purpose programming language, so the thesis is equivalent to saying that any general-purpose programming language is sufficient to express any algorithm. Various variations of the thesis exist; for example, the Physical Church–Turing thesis (PCTT) states: :"Every function that can be physically computed can be computed by a Turing machine." This stronger statement may have been proven false in 2002 when Willem Fouché discovered that a Turing machine probably cannot effectively approximate any of the values of one-dimensional Brownian motion at rational points in time (with respect to Wiener measure; see reference below). Another variation is the Strong Church–Turing thesis (SCTT), which states (cf. Bernstein, Vazirani 1997): :"Any 'reasonable' model of computation can be efficiently simulated on a probabilistic Turing machine."

History

The thesis is named after mathematicians Alonzo Church and Alan Turing. In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" Alan Turing tried to capture the notion of algorithm (then called "effective computability"), with the introduction of Turing machines. In that paper he showed that the 'Entscheidungsproblem' could not be solved. A few months earlier Alonzo Church had proven a similar result in "A Note on the Entscheidungsproblem" but he used the notions of recursive functions and lambda-definable functions to formally describe effective computability. Lambda-definable functions were introduced by Alonzo Church and Stephen Kleene (Church 1932, 1936a, 1941, Kleene 1935), and recursive functions were introduced by Kurt Gödel and Jacques Herbrand (Gödel 1934, Herbrand 1932). These two formalisms describe the same set of functions, as was shown in the case of functions of positive integers by Church and Kleene (Church 1936a, Kleene 1936). After hearing of Church's proposal, Turing was quickly able to show that his Turing machines in fact describe the same set of functions (Turing 1936, 263ff).

Success of the thesis

Since that time, many other formalisms for describing effective computability have been proposed, including recursive functions, the lambda calculus, register machines, Post systems, combinatory logic, and Markov algorithms. All these systems have been shown to compute the same functions as Turing machines; systems like this are called Turing-complete. Because all these different attempts of formalizing the concept of algorithm have yielded equivalent results, it is now generally assumed that the Church–Turing thesis is correct. However, the thesis is a definition and not a theorem, and hence cannot be proved true. It could, however, be disproved if a method could be exhibited which is universally accepted as being an effective algorithm but which cannot be performed on a Turing machine. In the early twentieth century, mathematicians often used the informal phrase effectively computable, so it was important to find a good formalization of the concept. Modern mathematicians instead use the well-defined term Turing computable (or computable for short). Since the undefined terminology has faded from use, the question of how to define it is now less important. The success of the Church–Turing thesis prompted supertheses that extend the thesis, including the conjecture that there is a polynomial transformation from the representation of computable functions in one formalization to their representation in another, and the conjecture that every model of computation can be step-by-step simulated by a Turing machine.

Philosophical implications

The Church–Turing thesis has some profound implications for the philosophy of mind. There are also some important open questions which cover the relationship between the Church–Turing thesis and physics, and the possibility of hypercomputation. When applied to physics, the thesis has several possible meanings: #The universe is equivalent to a Turing machine (and thus, computing non-recursive functions is physically impossible). This has been termed the strong Church–Turing thesis (not to be confused with the previously mentioned SCTT) and is a foundation of digital physics. #The universe is not a Turing machine (i.e., the laws of physics are not Turing-computable), but incomputable physical events are not "harnessable" for the construction of a hypercomputer. For example, a universe in which physics involves real numbers, as opposed to computable reals, might fall into this category. #The universe is a hypercomputer, and it is possible to build physical devices to harness this property and calculate non-recursive functions. For example, it is an open question whether all quantum mechanical events are Turing-computable, although it has been proved that any system built out of qubits is (at best) Turing-complete. John Lucas (and more famously, Roger Penrose) have suggested that the human mind might be the result of quantum hypercomputation, although there is little scientific evidence for this theory. There are many other technical possibilities which fall outside or between these three categories, but these serve to illustrate the range of the concept.

Reference

- Bernstein, E. & Vazirani, U. Quantum complexity theory, SIAM Journal on Computing 26(5) (1997) 1411?1473
- Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
- Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
- Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
- Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
- Fouché, W., Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
- Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
- Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
- Hofstadter, Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter 17.
- Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
- Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
- Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
- Turing, A.M., 1936, "[http://www.abelard.org/turpap2/tp2-ie.asp On Computable Numbers, with an Application to the Entscheidungsproblem]", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
- Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.

External links

- [http://plato.stanford.edu/entries/church-turing/ Detailed info on the Church–Turing Hypothesis] (Stanford Encyclopedia of Philosophy) Category:Recursion theory Category:Alan Turing Category:Theory of computation ko:처치-튜링 명제

Personal digital assistant

Personal digital assistants (PDAs or palmtops) are handheld devices that were originally designed as personal organizers, but became much more versatile over the years. A basic PDA usually includes date book, address book, task list, memo pad, clock, and calculator software. Many PDAs can now access the Internet via Wi-Fi or Bluetooth technology. One major advantage of using PDAs is their ability to synchronize data with a PC or home computer.

Overview

The term "personal digital assistant" was coined on January 7, 1992 by John Sculley at the Consumer Electronics Show in Las Vegas, Nevada, referring to the Apple Newton. Earlier devices like the Psion and Sharp Wizard have the functionality to be considered PDAs, however. The currently major PDA operating systems are:
- Palm OS - owned by Palm, Inc.
- Windows Mobile (Pocket PC), (based on the Windows CE kernel) - owned by Microsoft
- BlackBerry - owned by Research In Motion
- Many operating systems based on the Linux kernel - free (not owned by any company) These include:
- GPE - Based on GTK+/X11
- OPIE/Qtopia - based on Qt/E Qtopia is developed by Trolltech, OPIE is a fork of Qtopia developed by volunteers
- Symbian OS (formerly EPOC) owned by Ericsson, Panasonic, Nokia, Samsung, Siemens and Sony Ericsson Many PDAs run using a variation of the ARM architecture (usually denoted by the Intel Xscale trademark). This encompasses a class of RISC microprocessors that are widely used in mobile devices and embedded systems, and its design was influenced strongly by a popular 1970s/1980s CPU, the MOS Technology 6502. In its classic instant-on, silent operation, restricted storage and space, and single-tasking UI approach, the PDA can be seen as a logical descendent of the low power consumption, compact, limited capacity home computer popular during the late 1970s and 1990s. This class of machines has been largely replaced by descendents of the IBM PC that generally feature long boot-up times, fast execution CPUs that require active, noisy cooling, and very large capacity hard drives that produce additional noise and heat. According to a Gartner market study, the overall market for PDAs shrank by 5% in the first quarter (Q1) of 2004, compared to Q1 2003, with marketshare resolving as follows (by operating system):
- Palm OS for Palm, Inc. PDAs and some other licensees- 40.5% (stable)
- Windows Mobile for PDAs that comply with the Microsoft's Pocket PC specifications - 40.4% (slightly increasing)
- BlackBerry OS for BlackBerry PDA (produced by Research In Motion) - 14.8% (strongly increasing)
- Various operating systems based on the Linux kernel for [http://www.linuxdevices.com/articles/AT8728350077.html various special designed PDAs] ([http://tuxmobil.org/pda_linux.html many other supported]) - 1.9% (stable)
- Other - 2.4% (strongly decreasing) The reason usually cited for this decline is the growing capabilities of smartphones — mobile phones with PDA-like communication abilities.

Popular PDAs

mobile phone
- Apple Computer Newton
- BlackBerry
- hp iPAQ Pocket PC (Originally Compaq iPAQ until HP merged in 2002)
- Palm Pilot, Tungsten, LifeDrive, Treo and Zire
- Sharp Wizard and Zaurus
- Sony CLIÉ
- Tapwave Zodiac
- AlphaSmart Dana
- Dell Axim
- GMate Yopy
- Fujitsu Siemens Loox 720
- List of PalmOS Devices

Other uses

- Media player
- Audio recorder
- Camera (still & video)
- Remote control
- Wifi clients
- Video game emulator
- Photo browser
- GPS receiver
- Cell Phone
- Data Storage Device

External links

- [http://home.planet.nl/~hend2438/MOTW/r1-ModernMedicine/palm/ Collection of links to PDA sites]
- [http://www.pdacortex.com PDA cortex The Journal of Mobile Informatics]A Site dedicated to the use of PDAs in Nursing and [http://en.wikipedia.org/wiki/Nursing_Informatics Nursing Informtics ]
- [http://www.snarc.net/pda/pda-treatise.htm The evolution of PDAs, 1975-1995]
- [http://www.hellomobile.com/palm-vs-pocket-pc.htm Palm vs PocketPC Differences]
- [http://members.chello.nl/epzachte/Wikipedia/ Wikipedia on your PDA]
- [http://www.dslinux.org/ port of Linux for the Nintendo DS]
- [http://www.pdaid.com/ PDAid, Help for all PDAs]
- [http://www.wacklepedia.com/pdahotspots/pda_hotspots.htm PDA Hotspots] Sites suitable for small screen PDA's
- [http://tuxmobil.org/pda_linux.html Linux on PDAs and Handheld PCs]
- [http://repair4pda.org/ Repair and upgrade instructions for PDAs]
- [http://medpda.net medPDA.net Medical application reviews, news, discussions.]
- [http://www.palmflying.com/ PalmFLYING.com] Site that focuses on using PDAs in Aviation.
- [http://pda.en.wapedia.org Wapedia.org] - Wikipedia for PDAs
- [http://wikijserver.achterliek.de/ Wikipedia on your PDA and from CD, DVD]
- Category:Mobile computer ko:PDA ja:携帯情報端末

Supercomputer

A supercomputer is a computer that leads the world in terms of processing capacity, particularly speed of calculation, at the time of its introduction. (The term Super Computing was first used by New York World newspaper in 1920 to refer to the large custom built tabulators IBM had made for Columbia University.) Supercomputers introduced in the 1960s were designed primarily by Seymour Cray at Control Data Corporation (CDC), and led the market into the 1970s until Cray left to form his own company, Cray Research. He then took over the supercomputer market with his new designs, holding the top spot in supercomputing for 5 years (1985–1990). In the 1980s a large number of smaller competitors entered the market, in a parallel to the creation of the minicomputer market a decade earlier, but many of these disappeared in the mid-1990s "supercomputer market crash". Today, supercomputers are typically one-of-a-kind custom designs produced by "traditional" companies such as IBM and HP, who had purchased many of the 1980s companies to gain their experience, although Cray Inc. still specializes in building supercomputers. Cray Inc. The term supercomputer itself is rather fluid, and today's supercomputer tends to become tomorrow's also-ran. CDC's early machines were simply very fast scalar processors, some ten times the speed of the fastest machines offered by other companies. In the 1970s most supercomputers were dedicated to running a vector processor, and many of the newer players developed their own such processors at lower price points to enter the market. The early and mid-1980s saw machines with a modest number of vector processors working in parallel become the standard. Typical numbers of processors were in the range 4–16. In the later 1980s and 1990s, attention turned from vector processors to massive parallel processing systems with thousands of "ordinary" CPUs; some being off the shelf units and others being custom designs. Today, parallel designs are based on "off the shelf" RISC microprocessors, such as the PowerPC or PA-RISC, and most modern supercomputers are now highly-tuned computer clusters using commodity processors combined with custom interconnects.

Software tools

Software tools for distributed processing include standard APIs such as MPI and PVM, and open source-based software solutions such as Beowulf and openMosix which facilitate the creation of a sort of "virtual supercomputer" from a collection of ordinary workstations or servers. Technology like ZeroConf (Rendezvous/Bonjour) pave the way for the creation of ad hoc computer clusters. An example of this is the distributed rendering function in Apple's Shake compositing application. Computers running the Shake software merely need to be in proximity to each other, in networking terms, to automatically discover and use each other's resources. While no one has yet built an ad hoc computer cluster that rivals even yesteryear's supercomputers, the line between desktop, or even laptop, and supercomputer is beginning to blur, and is likely to continue to blur as built-in support for parallelism and distributed processing increases in mainstream desktop operating systems. An easy programming language for supercomputers remains an open research topic in Computer Science.

Uses

Supercomputers are used for highly calculation-intensive tasks such as weather forecasting, climate research (including research into global warming), molecular modeling (computing the structures and properties of chemical compounds, biological macromolecules, polymers, and crystals), physical simulations (such as simulation of airplanes in wind tunnels, simulation of the detonation of nuclear weapons, and research into nuclear fusion), cryptanalysis, and the like. Military and scientific agencies are heavy users.

Design

Supercomputers traditionally gained their speed over conventional computers through the use of innovative designs that allow them to perform many tasks in parallel, as well as complex detail engineering. They tend to be specialized for certain types of computation, usually numerical calculations, and perform poorly at more general computing tasks. Their memory hierarchy is very carefully designed to ensure the processor is kept fed with data and instructions at all times—in fact, much of the performance difference between slower computers and supercomputers is due to the memory hierarchy. Their I/O systems tend to be designed to support high bandwidth, with latency less of an issue, because supercomputers are not used for transaction processing. As with all highly parallel systems, Amdahl's law applies, and supercomputer designs devote great effort to eliminating software serialization, and using hardware to accelerate the remaining bottlenecks.

Supercomputer challenges, technologies

- A supercomputer generates large amounts of heat and must be cooled. Cooling most supercomputers is a major HVAC problem.
- Information cannot move faster than the speed of light between two parts of a supercomputer. For this reason, a supercomputer that is many meters across must have latencies between its components measured at least in the tens of nanoseconds. Seymour Cray's supercomputer designs attempted to keep cable runs as short as possible for this reason: hence the cylindrical shape of his famous Cray range of computers.
- Supercomputers consume and produce massive amounts of data in a very short period of time. According to Ken Batcher, "A supercomputer is a device for turning compute-bound problems into I/O-bound problems." Much work on external storage bandwidth is needed to ensure that this information can be transferred quickly and stored/retrieved correctly. Technologies developed for supercomputers include:
- Vector processing
- Liquid cooling
- Non-Uniform Memory Access (NUMA)
- Striped disks (the first instance of what was later called RAID)
- Parallel filesystems

Processing techniques

Vector processing techniques were first developed for supercomputers and continue to be used in specialist high-performance applications. Vector processing techniques have trickled down to the mass market in DSP architectures and SIMD processing instructions for general-purpose computers. Modern video game consoles in particular use SIMD extensively and this is the basis for some manufacturers' claim that their game machines are themselves supercomputers. Indeed, some graphics cards indeed have the computing power of several TeraFLOPS However, their uses are very limited.

Operating systems

Supercomputer operating systems, today most often variants of UNIX, are every bit as complex as those for smaller machines, if not more so. Their user interfaces tend to be less developed however, as the OS developers have limited programming resources to spend on non-essential parts of the OS (i.e., parts not directly contributing to the optimal utilization of the machine's hardware). This stems from the fact that because these computers, often priced at millions of dollars, are sold to a very small market, their R&D budgets are often limited. Interestingly this has been a continuing trend throughout the supercomputer industry, with former technology leaders such as Silicon Graphics taking a backseat to such companies as NVIDIA, who have been able to produce cheap, feature rich, high-performance, and innovative products due to the vast number of consumers driving their R&D. Historically, until the early-to-mid-1980s, supercomputers usually sacrificed instruction set compatibility and code portability for performance (processing and memory access speed). For the most part, supercomputers to this time (unlike high-end mainframes) had vastly different operating systems. The Cray-1 alone had at least six different proprietary OSs largely unknown to the general computing community. Similarly different and incompatible vectorizing and parallelizing compilers for Fortran existed. This trend would have continued with the ETA-10 were it not for the initial instruction set compatibility between the Cray-1 and the Cray X-MP, and the adoption of UNIX operating system variants (such as Cray's UniCOS). For this reason, in the future, the highest performance systems are likely to have a UNIX flavor but with incompatible system unique features (especially for the highest end systems at secure facilities).

Programming

The parallel architectures of supercomputers often dictate the use of special programming techniques to exploit their speed. Special-purpose Fortran compilers can often generate faster code than the C or C++ compilers, so Fortran remains the language of choice for scientific programming, and hence for most programs run on supercomputers. To exploit the parallelism of supercomputers, programming environments such as PVM and MPI for loosely connected clusters and OpenMP for tightly coordinated shared memory machines are being used.

Types of general-purpose supercomputers

There are three main classes of general-purpose supercomputers:
- Vector processing machines allow the same (arithmetical) operation to be carried out on a large amount of data simultaneously.
- Tightly connected cluster computers use specially developed interconnects to have many processors and their memory communicate with each other, typically in a NUMA architecture. Processors and networking components are engineered from the ground up for the supercomputer. The fastest general-purpose supercomputers in the world today use this technology.
- Commodity clusters use a large number of commodity PCs, interconnected by high-bandwidth low-latency local area networks. As of 2005, Moore's Law and economies of scale are the dominant factors in supercomputer design: a single modern desktop PC is now more powerful than a 15-year old supercomputer, and at least some of the design tricks that allowed past supercomputers to out-perform contemporary desktop machines have now been incorporated into commodity PCs. Furthermore, the costs of chip development and production make it uneconomical to design custom chips for a small run and favor mass-produced chips that have enough demand to recoup the cost of production. Additionally, many problems carried out by supercomputers are particularly suitable for parallelization (in essence, splitting up into smaller parts to be worked on simultaneously) and, particularly, fairly coarse-grained parallelization that limits the amount of information that needs to be transferred between independent processing units. For this reason, traditional supercomputers can be replaced, for many applications, by "clusters" of computers of standard design which can be programmed to act as one large computer.

Special-purpose supercomputers

Special-purpose supercomputers are high-performance computing devices with a hardware architecture dedicated to a single problem. This allows the use of specially programmed FPGA chips or even custom VLSI chips, allowing higher price/performance ratios by sacrificing generality. They are used for applications such as astrophysics computation and brute-force codebreaking. Examples of special-purpose supercomputers:
- Deep Blue, for playing chess
- Reconfigurable computing machines or parts of machines
- GRAPE, for astrophysics
- Deep Crack, for breaking the DES cipher

The fastest supercomputers today

Measuring supercomputer speed

The speed of a supercomputer is generally measured in "FLOPS" (FLoating Point Operations Per Second); this measurement is based on a particular benchmark, which mimics a class of real-world problems, but is significantly easier to compute than a majority of actual real-world problems.

Current fastest supercomputer system

benchmark On March 25, 2005, IBM's Blue Gene/L prototype became the fastest supercomputer in a single installation using its 32,768 processors to run at 280.6 TFLOPS (10¹² FLOPS). The Blue Gene/L prototype is a customized version of IBM's PowerPC architecture. The prototype was developed at IBM's Rochester, Minnesota facility, but production versions were rolled out to various sites, including Lawrence Livermore National Laboratory (LLNL). On October 28, 2005 the machine reached 280.6 TFLOPS, but the LLNL system is expected to achieve at least 360 TFLOPS, and a future update will take it to 0.5 PFLOPS. Before this, a Blue Gene/L fitted with 131,072 processors managed seven hours of sustained calculating at a 101.5 teraflops—another first. [http://news.bbc.co.uk/1/hi/technology/4386404.stm] In November of 2005 IBM Blue Gene/L became the number 1 on TOP500's most powerful supercomputer list.[http://www.top500.org/lists/2005/11/basic] The Google server farm constitutes one of the most powerful supercomputers in the world.

Previous fastest supercomputer system

Prior to Blue Gene/L, the fastest supercomputer was the NEC Earth Simulator at the Yokohama Institute for Earth Sciences, Japan. It is a cluster of 640 custom-designed 8-way vector processor computers based on the NEC SX-6 architecture (a total of 5,120 processors). It uses a customised version of the UNIX operating system. At the time of introduction, the Earth Simulator's performance was over five times that of the previous fastest supercomputer, the cluster computer ASCI White at Lawrence Livermore National Laboratory. The Earth Simulator held the #1 position for 2½ years. Because it was largely unanticipated by the top performers at the time, its introduction spawned the term "computnik," in a reference to the Soviet Union's upstaging of the Western space program with the 1957 launch of Sputnik. A list of the 500 fastest supercomputer installations, the TOP500, is maintained at http://www.top500.org/ .

Quasi-supercomputing

Some types of large-scale distributed computing for embarrassingly parallel problems take the clustered supercomputing concept to an extreme. One such example, the SETI@home distributed computing project has an average processing power of 72.53 TFLOPS [http://setiathome.berkeley.edu/totals.html]. On May 16 2005, the distributed computing project Folding@home reported a processing power of 195 TFLOPS on their CPU statistics page.[http://vspx27.stanford.edu/cgi-bin/main.py?qtype=cpustats]. Still higher powers have occasionally been recorded: on February 2 2005, 207 TFLOPS were noted as coming from Windows, Mac, and Linux clients [http://castlecops.com/t103306-Folding_Home_News.html]. GIMPS distributed Mersenne Prime search achieves currently 18 TFLOPS. Google's search engine system may be faster with estimated total processing power of between 126 and 316 TFLOPS. Tristan Louis estimates the systems to be composed of between 32,000 and 79,000 dual 2 GHz Xeon machines. [http://www.tnl.net/blog/entry/How_many_Google_machines] Since it would be logistically difficult to cool so many servers at one site, Google's system would presumably be another form of distributed computing project: grid computing.

Timeline of supercomputers

Historical and present:

External links

Information resources

- [http://www.top500.org/ TOP500 Supercomputer list]
- [http://www.linuxhpc.org/ Linux High Performance Computing and Clustering]
- [http://www.paralogos.com/DeadSuper/Projects.html Dead Supercomputer]
- [http://www.clusterresources.com Cluster Resources]
- [http://www.clusterbuilder.org Cluster Builder]

Supercomputing centers, organizations

- [http://www.hpcx.ac.uk HPCx] UK national supercomputer service operated by EPCC and Daresbury Lab
- [http://www.csar.cfs.ac.uk CSAR] UK national supercomputer service operated by [http://www.mc.manchester.ac.uk Manchester Computing]
- [http://www.hpc-uk.ac.uk HPC-UK] strategic collaboration between the UK's three leading supercomputer centres - Manchester Computing, EPCC and Daresbury Laboratory
- [http://www.sdsc.edu San Diego Supercomputer Center (SDSC)]
- [http://www.teragrid.org Teragrid]
- [http://www.westgrid.ca/support/topics/scheduling.php WestGrid]
- [http://www.tcf.vt.edu/systemX.html VirginiaTech]
- [http://www.irb.hr/en/cir/projects/dcc/00006/ IRB]
- [http://www.sara.nl/userinfo/lisa/usage/batch/index.html SARA]
- [http://www.psc.edu/ Pittsburgh Supercomputing Center] operated by University of Pittsburgh and Carnegie Mellon University.
- [http://www.LinuxHPC.org LinuxHPC.org]

Specific machines, general-purpose

- [http://www.wswinteractive.com/hp/pnnl/default.htm HP announcement of contract to build Linux supercomputer]
- [http://lwn.net/Articles/4759/ Linux NetworkX press release: Linux NetworX to build "largest" Linux supercomputer]
- [http://www.llnl.gov/asci/news/white_news.html ASCI White press release]
- [http://www.hoise.com/primeur/02/articles/weekly/AE-PR-05-02-59.html Article about Japanese "Earth Simulator" computer]
- [http://www.es.jamstec.go.jp/esc/eng/ "Earth Simulator" website (in English)]
- [http://www.nec.com.sg/necsin/hpcs.htm NEC high-performance computing information]
- [http://www.hq.nasa.gov/hpcc/insights/vol6/supercom.htm Superconducting Supercomputer]

Specific machines, special-purpose

- [http://grape.c.u-tokyo.ac.jp/gp/paper/hardpaper.html Papers on the GRAPE special-purpose computer]
- [http://big.gsc.riken.go.jp/SPCtext.htm More special-purpose supercomputer information]
- [http://chimera.roma1.infn.it/apehdoc/apemille/INFN_APEmille.html Information about the APEmille special-purpose computer]
- [http://phys.columbia.edu/~cqft/ Information about the QCDOC project, machines]
- Supercomputer ko:슈퍼 컴퓨터 ms:Superkomputer ja:スーパーコンピュータ

Moore's law

Moore's law is a rule of thumb in the computer industry about the growth of computing power over time. Attributed to Gordon E. Moore the co-founder of Intel, it states that the growth of computing power follows an empirical exponential law. Moore originally proposed a 12 month doubling and, later, a 24 month period. This 'law' can be interpreted with varying degrees of rigor and frequently is. The least rigorous interpretation of Moore's law is that computing power per unit cost will continue to grow exponentially. In this form, "Moore's law" has a factual basis and has proven useful for planning purposes. The most rigorous interpretation of Moore's law is that the total number of transistors on the cheapest CPU will grow exponentially at a constant rate and that this constant rate produces a doubling every 12 (or 18, or 24) months. This variant oversimplifies a complex history. Gordon E. Moore

Problems

The key problem with the process of finding evidence to support a rigorous interpretation of Moore's law lies in the use of multiple fudge factors. These include:
- The choice of CPUs to look at - low-end or high-end, from Intel or some other manufacturer.
- The choice of point in a CPU's lifecycle - when introduced, when mass produced or when their production has been optimized.
- The cost of the CPU - in constant dollars adjusted for inflation, from which source, applying what discounts.
- Uncertainties inherent in accounting for clocking differences. Additionally, the choice of chart can make seeing whether the data actually fit the curve difficult for people who are not very familiar with exponential curves. Sometimes, the charts advanced as evidence actually disprove the interpretation of Moore's law which is claimed to be true. In summary, evidence for a rigorous interpretation of Moore's law cannot be considered scientific when the process by which it is gathered and interpreted is not disclosed. The few scientific investigations of Moore's law have concluded that a rigorous interpretation of it is not possible. Nonetheless, the law, interpreted generally, has held for far longer than most authorities at the time would have believed and many experts expect its growth predictions to hold for the next decade or more.

Earliest forms

Moore's original statement can be found in his publication "Cramming more components onto integrated circuits", Electronics Magazine 19 April, 1965:

The complexity for minimum component costs has increased at a rate of roughly a factor of two per year ... Certainly over the short term this rate can be expected to continue, if not to increase. Over the longer term, the rate of increase is a bit more uncertain, although there is no reason to believe it will not remain nearly constant for at least 10 years. That means by 1975, the number of components per integrated circuit for minimum cost will be 65,000. I believe that such a large circuit can be built on a single wafer.

Under the assumption that chip "complexity" is proportional to the number of transistors, regardless of what they do, the law has notably not held up to the test of time. In 1975,

"Moore's 1965 prediction that in 1975 the most cost efficient chips would incorporate 65,000 components was, in fact, wrong. The chip that Moore used in his 1975 presentation to show that his earlier prediction had been accurate, was a charge-coupled memory device that was just about to be introduced and it didn't have 64,000 components. Such a chip, therefore, strictly speaking did not exist. Furthermore it probably did not represent the most cost efficient chip, as it was quickly withdrawn from production. Indeed, the cost structure of different chip types had already become differentiated. In 1975 Intel introduced its first general purpose 8080 processor that started the PC revolution. It had 4,500 transistors.
— [http://firstmonday.org/issues/issue7_11/tuomi/index.html (The Lives and Death of Moore's Law)]

Gordon Moore's observation was not named a "law" by Moore himself; that honor goes to Caltech professor, VLSI pioneer, and entrepreneur Carver Mead. In 1975, Moore projected a doubling only every two years. He is adamant that he himself never said "every 18 months", but that is how it has been quoted. The SEMATECH roadmap follows a 24 month cycle. In April 2005 Intel paid $10,000 to purchase a copy of the Electronics Magazine issue containing the original article.

Formulations of Moore's law

The most popular formulation is of the doubling of the number of transistors on integrated circuits (a rough measure of computer processing power) every 18 months. At the end of the 1970s, Moore's Law became known as the limit for the number of transistors on the most complex chips. However, it is also common to cite Moore's law to refer to the rapidly continuing advance in computing power per unit cost. While growth has been continuous, no conceivable 'constant growth' law has held for hard disk storage cost per unit of information. The rate of growth in disk storage has been very uneven over the past decades and has markedly sped up more than once, corresponding to the utilization of error correcting codes, the magnetoresistive effect and the giant magnetoresistive effect. The current rate of increase in hard drive capacity is much faster than the rate of increase in transistor count and has been dubbed Kryder's law. Another version claims that RAM storage capacity increases at the same rate as processing power. However, memory speeds have not increased as fast as CPU speeds in recent years, leading to a heavy reliance on caching in current computer systems.

An industry driver

Although Moore's law was initially made in the form of an observation and prediction, the more widely it became accepted, the more it served as a goal for an entire industry. This drove both marketing and engineering departments of semiconductor manufacturers to focus enormous energy aiming for the specified increase in processing power that it was presumed one or more of their competitors would soon actually attain. In this regard it can be viewed as a self-fulfilling prophecy. The implications of Moore's law for computer component suppliers is very significant. A typical major design project (such as an all-new CPU or hard drive) takes between two and five years to reach production-ready status. In consequence, component manufacturers face enormous timescale pressures—just a few weeks' delay in a major project can spell the difference between great success and massive losses, even bankruptcy. Expressed as "a doubling every 18 months", Moore's law suggests the phenomenal progress of technology in recent years. Expressed on a shorter timescale, however, Moore's law equates to an average performance improvement in the industry as a whole of over 1% a week. For a manufacturer competing in the cut-throat CPU market, a new product that is expected to take three years to develop and is just two or three months late is 10 to 15% slower, bulkier, or lower in storage capacity than the directly competing products, and is usually unsellable.

Future trends

As of Q4 2004, current PC processors are fabricated at the 130 nm and 90 nm levels, with 65 nm chips being announced by the end of 2005. A decade ago, chips were built at a 500 nm level. Companies are working on using nanotechnology to solve the complex engineering problems involved in producing chips at the 45 nm, 30 nm, and even smaller levels—a process that will postpone the industry meeting the limits of Moore's Law. Recent computer [http://public.itrs.net/ industry technology "roadmaps"] predict (as of 2001) that Moore's Law will continue for several chip generations. Depending on the doubling time used in the calculations, this could mean up to 100 fold increase in transistor counts on a chip in a decade. The semiconductor industry technology roadmap uses a three-year doubling time for microprocessors, leading to about nine-fold increase in a decade. Since the rapid exponential improvement could (in theory) put 100 GHz personal computers in every home and 20 GHz devices in every pocket, some commentators have speculated that sooner or later computers will meet or exceed any conceivable need for computation. This is only true for some problems—there are others where exponential increases in processing power are matched or exceeded by exponential increases in complexity as the problem size increases. See computational complexity theory and complexity classes P and NP for a (somewhat theoretical) discussion of such problems, which occur very commonly in applications such as scheduling. Extrapolation partly based on Moore's Law has led futurologists such as Vernor Vinge, Bruce Sterling and Ray Kurzweil to speculate about a technological singularity. However, on April 13, 2005, Gordon Moore himself stated in an interview that the law may not hold valid for too long, since transistors may reach the limits of miniaturization at atomic levels.

In terms of size [of transistor] you can see that we're approaching the size of atoms which is a fundamental barrier, but it'll be two or three generations before we get that far—but that's as far out as we've ever been able to see. We have another 10 to 20 years before we reach a fundamental limit. By then they'll be able to make bigger chips and have transistor budgets in the billions.
—[http://www.techworld.com/opsys/news/index.cfm?NewsID=3477 (techworld)]

2005 to earlier transistors, vacuum tubes, relays and electromechanical computers.]] Kurzweil replies that although around the year 2019, if Moore's Law keeps up, transistor features will be just a few atoms in width, and the strategy of ever finer photolithography will have run its course, this does not mean the end of Moore's Law. He notes that:

Moore's Law of Integrated Circuits was not the first, but the fifth paradigm to provide accelerating price-performance. Computing devices have been consistently multiplying in power (per unit of time) from the mechanical calculating devices used in the 1890 U.S. Census, to Turing's relay-based "Robinson" machine that cracked the Nazi enigma code, to the CBS vacuum tube computer that predicted the election of Eisenhower, to the transistor-based machines used in the first space launches, to the integrated-circuit-based personal computers.
—[http://www.kurzweilai.net/articles/art0134.html?printable=1 (Kurzweil net)]

Thus Kurzweil concludes that it is likely that some new type of technology will replace current integrated-circuit technology, and Moore's Law will hold true long after 2020. Kurzweil extends his analysis to include technologies from far before the integrated circuit to future forms of computation. He believes that the exponential growth of Moore's Law will continue beyond the use of integrated circuits into technologies that will lead to the technological singularity. The Law of Accelerating Returns described by Ray Kurzweil has in many ways altered the public's perception of Moore's law. It is a common (but mistaken) belief that Moore's Law makes predictions regarding all forms of technology, when really it only concerns semiconductor circuits. Many futurists still use the term "Moore's Law" to describe ideas like those put forth by Kurzweil. Krauss and Starkman announced an ultimate limit of around 600 years in their paper [http://arxiv.org/abs/astro-ph/0404510&e=10129 "Universal Limits of Computation"], based on rigorous estimation of total information-processing capacity of any system in the Universe. Then again, the law has often met obstacles that appeared insurmountable, before soon surmounting them. In that sense, Mr. Moore says, he now sees his law as more beautiful than he had realised. "Moore's Law is a violation of Murphy's Law. Everything gets better and better." [http://economist.com/displaystory.cfm?story_id=3798505]

Other considerations

Not all aspects of computing technology develop in capacities and speed according to Moore's Law. Random Access Memory (RAM) speeds and hard drive seek times improve at best a few percentages per year. Another, sometimes misunderstood, point is that exponentially improved hardware does not necessarily imply exponentially improved software to go with it. The productivity of software developers most assuredly does not increase exponentially with the improvement in hardware, but by most measures has increased only slowly and fitfully over the decades. Software tends to get larger and more complicated over time, and Wirth's law even states that "Software gets slower faster than hardware gets faster". Moreover there is popular misconception that the clock speed of a processor determines its speed. This actually also depends on the number of instructions per tick which can be executed (as well as the complexity of each instruction, see MIPS, RISC and CISC), and as such the clock speed can only be used for comparison between two identical circuits. Of course, other factors are to be taken into consideration such as the bus size and speed of the peripherals. As such, most popular evaluations of "computer speed" are generally biased without an understanding of the underlying technology. This is especially true now that popular manufacturers play with public perception of speed, focusing on advertising the clock rate of new products. It is interesting to note that as the cost of computer power continues to fall (from the perspective of a consumer), the cost for producers to achieve Moore's Law has followed the opposite trend: R&D, manufacturing, and test costs have increased steadily with each new generation of chips. As the cost of semiconductor equipment is expected to continue increasing, manufacturers must sell larger and larger quantities of chips to remain profitable. (The cost to "tapeout" a chip at 0.18u was roughly $300,000 USD. The cost to "tapeout" a chip at 90nm exceeds $750,000 USD, and the cost is expected to exceed $1.0M USD for 65nm.) In recent years, analysts have observed a decline in the number of "design starts" at advanced process nodes (0.13u and below.) While these observations were made in the period after the year 2000 economic downturn, the decline may be evidence that traditional manufacturers in the long-term global market cannot economically sustain Moore's Law.

Notes

# Not to be confused with another G.E. Moore, the philosopher George Edward Moore, the creator of Moore's paradox.

External links

Articles

- [http://www.intel.com/technology/mooreslaw/index.htm Intel's information page on Moore's Law] – With link to Moore's original 1965 paper
- [http://www.intel.com/pressroom/kits/events/moores_law_40th/index.htm Intel press kit] released for Moore's Law's 40th anniversary, with a [ftp://download.intel.com/pressroom/images/events/moores_law_40th/Moores_Law_Original_Graph.jpg 1965 sketch] by Moore
- [http://firstmonday.org/issues/issue7_11/tuomi/index.html The Lives and Death of Moore's Law] – By Ilkka Tuomi; a detailed study on Moore's law and its historical evolution
- [http://www.amdboard.com/mooreslaw.html Moore's Law Special at AMDboard] – All the pertinent links to Moore's law material
- [http://news.com.com/2100-1006_3-5607422.html Moore says nanoelectronics face tough challenges] – By Michael Kanellos, CNET News.com, 9 March, 2005
- [http://www.nytimes.com/2005/04/18/technology/18moore.html It's Moore's Law, But Another Had The Idea First] by John Markoff
- [http://economist.com/displaystory.cfm?story_id=3798505 Happy birthday: The tale of a frivolous rule of thumb], The Economist, March 23, 2005
- [http://news.bbc.co.uk/2/hi/science/nature/4449711.stm Law that has driven digital life: The Impact of Moore's Law] – A comprehensive BBC News article, 18 April, 2005

Data

- [http://www.xbitlabs.com/articles/cpu/display/p4-3200.html Intel Pentium 4 3.2GHz CPU Review] by X-bit labs June 23, 2003 – See "CPU frequency growth"

FAQs

- [http://news.com.com/FAQ+Forty+years+of+Moores+Law/2100-1006_3-5647824.html?tag=nefd.lede a C|net FAQ about Moore's Law] Category:Exponentials Category:Adages Category:Computing Category:Electronic design Category:Rules of thumb Category:Digital media Category:Digital Revolution Category:Eponymous laws Category:Futurology ko:무어의 법칙 ja:ムーアの法則

Computer

History of computing

How computers work: the stored program architecture

Digital circuits

I/O devices

Instructions

Programs

Libraries and operating systems

Computer applications

Networking and the Internet

Computing professions and disciplines

See also

References

Data

Etymology

Usage in English

Uses of data in computing

Meaning of data, information and knowledge

See also

References

Church-Turing Thesis

Church–Turing thesis

History

Success of the thesis

Philosophical implications

Reference

See also

External links

Personal digital assistant

Overview

Popular PDAs

Other uses

See also

External links

Supercomputer

Software tools

Uses

Design

Supercomputer challenges, technologies

Processing techniques

Operating systems

Programming

Types of general-purpose supercomputers

Special-purpose supercomputers

The fastest supercomputers today

Measuring supercomputer speed

Current fastest supercomputer system

Previous fastest supercomputer system

Quasi-supercomputing

Timeline of supercomputers

See also

General concepts, history

Other classes of computer

Supercomputer companies, operating

Supercomputer companies, defunct

External links

Information resources

Supercomputing centers, organizations

Specific machines, general-purpose

Specific machines, special-purpose

Moore's law

Problems

Earliest forms

Formulations of Moore's law

An industry driver

Future trends

Other considerations

Notes

See also

External links

Articles

Data

FAQs

Supercomputer