Misplaced Pages

#12987

56-410: Stanford DASH was a cache coherent multiprocessor developed in the late 1980s by a group led by Anoop Gupta, John L. Hennessy , Mark Horowitz , and Monica S. Lam at Stanford University . It was based on adding a pair of directory boards designed at Stanford to up to 16 SGI IRIS 4D Power Series machines and then cabling the systems in a mesh topology using

112-467: A 12-digit Standard Book Number of 345-24223-8-595 (valid SBN: 345-24223-8, ISBN: 0-345-24223-8), and it cost US$ 5.95 . Since 1 January 2007, ISBNs have contained thirteen digits, a format that is compatible with " Bookland " European Article Numbers , which have 13 digits. Since 2016, ISBNs have also been used to identify mobile games by China's Administration of Press and Publication . The United States , with 3.9 million registered ISBNs in 2020,

168-468: A Stanford-modified version of the Torus Routing Chip. The boards designed at Stanford implemented a directory-based cache coherence protocol allowing Stanford DASH to support distributed shared memory for up to 64 processors. Stanford DASH was also notable for both supporting and helping to formalize weak memory consistency models , including release consistency . Because Stanford DASH was

224-730: A cache coherent system, and all memory locations for a sequentially consistent system). Another definition is: "a multiprocessor is cache consistent if all writes to the same memory location are performed in some sequential order". Rarely, but especially in algorithms, coherence can instead refer to the locality of reference . Multiple copies of the same data can exist in different cache simultaneously and if processors are allowed to update their own copies freely, an inconsistent view of memory can result. The two most common mechanisms of ensuring coherency are snooping and directory-based , each having their own benefits and drawbacks. Snooping based protocols tend to be faster, if enough bandwidth

280-446: A coherent system is via the definition of sequential consistency memory model: "the cache coherent system must appear to execute all threads’ loads and stores to a single memory location in a total order that respects the program order of each thread". Thus, the only difference between the cache coherent system and sequentially consistent system is in the number of address locations the definition talks about (single memory location for

336-603: A copy of the memory location X. The following conditions are necessary to achieve cache coherence: The above conditions satisfy the Write Propagation criteria required for cache coherence. However, they are not sufficient as they do not satisfy the Transaction Serialization condition. To illustrate this better, consider the following example: A multi-processor system consists of four processors - P1, P2, P3 and P4, all containing cached copies of

392-451: A given ISBN is complicated, because most of the parts do not use a fixed number of digits. ISBN issuance is country-specific, in that ISBNs are issued by the ISBN registration agency that is responsible for that country or territory regardless of the publication language. The ranges of ISBNs assigned to any particular country are based on the publishing profile of the country concerned, and so

448-429: A read to S . P4 on the other hand may see changes made by P1 and P2 in the order in which they are made and hence return 20 on a read to S . The processors P3 and P4 now have an incoherent view of the memory. Therefore, in order to satisfy Transaction Serialization, and hence achieve Cache Coherence, the following condition along with the previous two mentioned in this section must be met: The alternative definition of

504-405: A shared variable S whose initial value is 0. Processor P1 changes the value of S (in its cached copy) to 10 following which processor P2 changes the value of S in its own cached copy to 20. If we ensure only write propagation, then P3 and P4 will certainly see the changes made to S by P1 and P2. However, P3 may see the change made by P1 after seeing the change made by P2 and hence return 10 on

560-458: A simple reprinting of an existing item. For example, an e-book , a paperback and a hardcover edition of the same book must each have a different ISBN, but an unchanged reprint of the hardcover edition keeps the same ISBN. The ISBN is ten digits long if assigned before 2007, and thirteen digits long if assigned on or after 1 January 2007. The method of assigning an ISBN is nation-specific and varies between countries, often depending on how large

616-401: A systematic pattern, which allows their length to be determined, as follows: A check digit is a form of redundancy check used for error detection , the decimal equivalent of a binary check bit . It consists of a single digit computed from the other digits in the number. The method for the 10-digit ISBN is an extension of that for SBNs, so the two systems are compatible; an SBN prefixed with

SECTION 10

#1732791084013

672-461: A zero (the 10-digit ISBN) will give the same check digit as the SBN without the zero. The check digit is base eleven, and can be an integer between 0 and 9, or an 'X'. The system for 13-digit ISBNs is not compatible with SBNs and will, in general, give a different check digit from the corresponding 10-digit ISBN, so does not provide the same protection against transposition. This is because the 13-digit code

728-564: A zero to a 9-digit SBN creates a valid 10-digit ISBN. The national ISBN agency assigns the registrant element ( cf. Category:ISBN agencies ) and an accompanying series of ISBNs within that registrant element to the publisher; the publisher then allocates one of the ISBNs to each of its books. In most countries, a book publisher is not legally required to assign an ISBN, although most large bookstores only handle publications that have ISBNs assigned to them. The International ISBN Agency maintains

784-533: A zero). Privately published books sometimes appear without an ISBN. The International ISBN Agency sometimes assigns ISBNs to such books on its own initiative. A separate identifier code of a similar kind, the International Standard Serial Number (ISSN), identifies periodical publications such as magazines and newspapers . The International Standard Music Number (ISMN) covers musical scores . The Standard Book Number (SBN)

840-477: Is 7, and the complete sequence is ISBN 978-0-306-40615-7. In general, the ISBN check digit is calculated as follows. Let Then This check system—similar to the UPC check digit formula—does not catch all errors of adjacent digit transposition. Specifically, if the difference between two adjacent digits is 5, the check digit will not catch their transposition. For instance, the above example allows this situation with

896-469: Is a commercial system using nine-digit code numbers to identify books. In 1965, British bookseller and stationers WHSmith announced plans to implement a standard numbering system for its books. They hired consultants to work on their behalf, and the system was devised by Gordon Foster , emeritus professor of statistics at Trinity College Dublin . The International Organization for Standardization (ISO) Technical Committee on Documentation sought to adapt

952-400: Is a multiple of 11. That is, if x i is the i th digit, then x 10 must be chosen such that: For example, for an ISBN-10 of 0-306-40615-2: Formally, using modular arithmetic , this is rendered It is also true for ISBN-10s that the sum of all ten digits, each multiplied by its weight in ascending order from 1 to 10, is a multiple of 11. For this example: Formally, this

1008-616: Is a write-invalidate protocol. However, scalability is one shortcoming of broadcast protocols. Various models and protocols have been devised for maintaining coherence, such as MSI , MESI (aka Illinois), MOSI , MOESI , MERSI , MESIF , write-once , Synapse, Berkeley, Firefly and Dragon protocol . In 2011, ARM Ltd proposed the AMBA 4 ACE for handling coherency in SoCs . The AMBA CHI (Coherent Hub Interface) specification from ARM Ltd , which belongs to AMBA5 group of specifications defines

1064-503: Is available on the International ISBN Agency website. A list for a few countries is given below: The ISBN registration group element is a 1-to-5-digit number that is valid within a single prefix element (i.e. one of 978 or 979), and can be separated between hyphens, such as "978-1-..." . Registration groups have primarily been allocated within the 978 prefix element. The single-digit registration groups within

1120-517: Is available, since all transactions are a request/response seen by all processors. The drawback is that snooping isn't scalable. Every request must be broadcast to all nodes in a system, meaning that as the system gets larger, the size of the (logical or physical) bus and the bandwidth it provides must grow. Directories, on the other hand, tend to have longer latencies (with a 3 hop request/forward/respond) but use much less bandwidth since messages are point to point and not broadcast. For this reason, many of

1176-402: Is not needed, but it may be considered to simplify the calculation.) For example, the check digit for the ISBN of 0-306-40615- ? is calculated as follows: Thus the check digit is 2. It is possible to avoid the multiplications in a software implementation by using two accumulators. Repeatedly adding t into s computes the necessary multiples: The modular reduction can be done once at

SECTION 20

#1732791084013

1232-414: Is rendered The two most common errors in handling an ISBN (e.g. when typing it or writing it down) are a single altered digit or the transposition of adjacent digits. It can be proven mathematically that all pairs of valid ISBN-10s differ in at least two digits. It can also be proven that there are no pairs of valid ISBN-10s with eight identical digits and two transposed digits (these proofs are true because

1288-719: Is used as a case study in contemporary computer science classes. References [ edit ] ^ Lenoski, Daniel; Laudon, James; Gharachorloo, Kourosh; Weber, Wolf-Dietrich; Gupta, Anoop; Hennessy, John; Horowitz, Mark; Lam, Monica S. (1992). "The Stanford Dash Multiprocessor" . Computer . 25 (3): 63–79. doi : 10.1109/2.121510 . S2CID   9731523 . ^ Dally, William J.; Seitz, Charles L. (1986). "The torus routing chip". Distributed Computing . 1 (4): 187–196. doi : 10.1007/BF01660031 . S2CID   10500442 . ^ Lenoski, Daniel; Laudon, James; Gharachorloo, Kourosh; Gupta, Anoop; Hennessy, John (1990). "The directory-based cache coherence protocol for

1344-410: Is used to maintain cache coherency. The two main types are snooping and directory-based protocols. Cache coherence is of particular relevance in multiprocessing systems, where each CPU may have its own local cache of a shared memory resource. In a shared memory multiprocessor system with a separate cache memory for each processor, it is possible to have many copies of shared data: one copy in

1400-415: The publisher , "01381" is the serial number assigned by the publisher, and "8" is the check digit . By prefixing a zero, this can be converted to ISBN   0-340-01381-8 ; the check digit does not need to be re-calculated. Some publishers, such as Ballantine Books , would sometimes use 12-digit SBNs where the last three digits indicated the price of the book; for example, Woodstock Handmade Houses had

1456-448: The 13-digit ISBN, as follows: A 13-digit ISBN can be separated into its parts ( prefix element , registration group , registrant , publication and check digit ), and when this is done it is customary to separate the parts with hyphens or spaces. Separating the parts ( registration group , registrant , publication and check digit ) of a 10-digit ISBN is also done with either hyphens or spaces. Figuring out how to correctly separate

1512-432: The 6 followed by a 1. The correct order contributes 3 × 6 + 1 × 1 = 19 to the sum; while, if the digits are transposed (1 followed by a 6), the contribution of those two digits will be 3 × 1 + 1 × 6 = 9 . However, 19 and 9 are congruent modulo 10, and so produce the same, final result: both ISBNs will have a check digit of 7. The ISBN-10 formula uses the prime modulus 11 which avoids this blind spot, but requires more than

1568-473: The 978-prefix element are: 0 or 1 for English-speaking countries; 2 for French-speaking countries; 3 for German-speaking countries; 4 for Japan; 5 for Russian-speaking countries; and 7 for People's Republic of China. Example 5-digit registration groups are 99936 and 99980, for Bhutan. The allocated registration groups are: 0–5, 600–631, 65, 7, 80–94, 950–989, 9910–9989, and 99901–99993. Books published in rare languages typically have longer group elements. Within

1624-583: The 979 prefix element, the registration group 0 is reserved for compatibility with International Standard Music Numbers (ISMNs), but such material is not actually assigned an ISBN. The registration groups within prefix element 979 that have been assigned are 8 for the United States of America, 10 for France, 11 for the Republic of Korea, and 12 for Italy. The original 9-digit standard book number (SBN) had no registration group identifier, but prefixing

1680-621: The British SBN for international use. The ISBN identification format was conceived in 1967 in the United Kingdom by David Whitaker (regarded as the "Father of the ISBN") and in 1968 in the United States by Emery Koltay (who later became director of the U.S. ISBN agency R. R. Bowker ). The 10-digit ISBN format was developed by the ISO and was published in 1970 as international standard ISO 2108. The United Kingdom continued to use

1736-977: The DASH multiprocessor". Proceedings of the 17th Annual International symposium on Computer Architecture . ACM. pp. 148–159. doi : 10.1145/325164.325132 . ^ Gharachorloo, Kourosh; Lenoski, Daniel; Laudon, James; Gibbons, Phillip; Gupta, Anoop; Hennessy, John (1990). "Memory consistency and event ordering in scalable shared-memory multiprocessors". Proceedings of the 17th annual international symposium on Computer Architecture . pp. 15–26. doi : 10.1145/325096.325102 . ^ Hennessy, John; Patterson, David (2003). Computer Architecture: A Quantitative Approach (Third ed.). Morgan Kaufmann. pp.  655 . ISBN   978-1-558-60596-1 . ^ Lenoski, Daniel; Laudon, James; Joe, Truman; Nakahira, David; Stevens, Luis; Gupta, Anoop; Hennessy, John (1998). "The DASH prototype: Implementation and Performance" . In Sohi, Gurindar (ed.). 25 years of

Stanford DASH - Misplaced Pages Continue

1792-416: The ISBN is less than eleven digits long and because 11 is a prime number ). The ISBN check digit method therefore ensures that it will always be possible to detect these two most common types of error, i.e., if either of these types of error has occurred, the result will never be a valid ISBN—the sum of the digits multiplied by their weights will never be a multiple of 11. However, if the error were to occur in

1848-1991: The International Symposia on Computer Architecture (Selected Papers) . pp. 418–429. ^ Suzuki, Norihisa (1992). Shared Memory Multiprocessing . The MIT Press. pp. 391–406. ISBN   978-0-262-19322-1 . ^ Loshin, David (1994). High Performance Computing Demystified . Academic Press. pp.  80, 91 . ISBN   978-0-124-55825-0 . ^ Parhami, Behrooz (1999). Introduction to Parallel Processing: Algorithms and Architectures . Springer. pp. 450–451. ISBN   978-0-306-45970-2 . ^ Hill, Mark; Jouppi, Norman ; Sohi, Gurindar (2000). Readings in Computer Architecture . Morgan Kaufmann. pp. 583–599. ISBN   978-1-55860-539-8 . ^ Dandamudi, Sivarama (2003). Hierarchical Scheduling in Parallel and Cluster Systems . Series in Computer Science. Springer US. pp.  21 –22. doi : 10.1007/978-1-4615-0133-6 . ISBN   978-1-4613-4938-9 . S2CID   46434929 . ^ Institute for Computing Systems Architecture, School of Informatics, University of Edinburgh "Stanford DASH Architecture: Cluster Simulation Model" , Retrieved on 3 November 2015. ^ Carl Olson and Mattan Erez, The University of Texas at Austin (2007) "The Stanford Dash Multiprocessor" , Retrieved on 3 November 2015. ^ Meng Zhang, Duke University (2010) "The Stanford Dash Multiprocessor" , Retrieved on 3 November 2015. Retrieved from " https://en.wikipedia.org/w/index.php?title=Stanford_DASH&oldid=1086302575 " Categories : Parallel computing Cluster computing Computers Cache coherency A cache coherence protocol

1904-657: The allocations of ISBNs that they make to publishers. For example, a large publisher may be given a block of ISBNs where fewer digits are allocated for the registrant element and many digits are allocated for the publication element; likewise, countries publishing many titles have few allocated digits for the registration group identifier and many for the registrant and publication elements. Here are some sample ISBN-10 codes, illustrating block length variations. English-language registration group elements are 0 and 1 (2 of more than 220 registration group elements). These two registration group elements are divided into registrant elements in

1960-425: The basic requirements for coherence. It can be tailor-made for the target system or application. Protocols can also be classified as snoopy or directory-based. Typically, early systems used directory-based protocols where a directory would keep a track of the data being shared and the sharers. In snoopy protocols, the transaction requests (to read, write, or upgrade) are sent out to all processors. All processors snoop

2016-466: The check digit itself). Each digit, from left to right, is alternately multiplied by 1 or 3, then those products are summed modulo 10 to give a value ranging from 0 to 9. Subtracted from 10, that leaves a result from 1 to 10. A zero replaces a ten, so, in all cases, a single check digit results. For example, the ISBN-13 check digit of 978-0-306-40615- ? is calculated as follows: Thus, the check digit

2072-419: The check digit must equal either 0 or 11. Therefore, the check digit is (11 minus the remainder of the sum of the products modulo 11) modulo 11. Taking the remainder modulo 11 a second time accounts for the possibility that the first remainder is 0. Without the second modulo operation, the calculation could result in a check digit value of 11 − 0 = 11 , which is invalid. (Strictly speaking, the first "modulo 11"

2128-411: The complete sequence is ISBN 0-306-40615-2. If the value of x 10 {\displaystyle x_{10}} required to satisfy this condition is 10, then an 'X' should be used. Alternatively, modular arithmetic is convenient for calculating the check digit using modulus 11. The remainder of this sum when it is divided by 11 (i.e. its value modulo 11), is computed. This remainder plus

2184-478: The details of over one million ISBN prefixes and publishers in the Global Register of Publishers . This database is freely searchable over the internet. Publishers receive blocks of ISBNs, with larger blocks allotted to publishers expecting to need them; a small publisher may receive ISBNs of one or more digits for the registration group identifier, several digits for the registrant, and a single digit for

2240-437: The end, as shown above (in which case s could hold a value as large as 496, for the invalid ISBN 99999-999-9-X), or s and t could be reduced by a conditional subtract after each addition. Appendix 1 of the International ISBN Agency's official user manual describes how the 13-digit ISBN check digit is calculated. The ISBN-13 check digit, which is the last digit of the ISBN, must range from 0 to 9 and must be such that

2296-542: The first operational machine to include scalable cache coherence, it influenced subsequent computer science research as well as the commercially available SGI Origin 2000 . Stanford DASH is included in the 25th anniversary retrospective of selected papers from the International Symposium on Computer Architecture and several computer science books, has been simulated by the University of Edinburgh , and

Stanford DASH - Misplaced Pages Continue

2352-411: The interfaces for the connection of fully coherent processors. ISBN (identifier) The International Standard Book Number ( ISBN ) is a numeric commercial book identifier that is intended to be unique. Publishers purchase or receive ISBNs from an affiliate of the International ISBN Agency. A different ISBN is assigned to each separate edition and variation of a publication, but not to

2408-418: The larger systems (>64 processors) use this type of cache coherence. Distributed shared memory systems mimic these mechanisms in an attempt to maintain consistency between blocks of memory in loosely coupled systems. Coherence protocols apply cache coherence in multiprocessor systems. The intention is that two clients must never see different values for the same shared data. The protocol must implement

2464-408: The load/store granularity . However, in practice it is generally performed at the granularity of cache blocks. Coherence defines the behavior of reads and writes to a single address location. One type of data occurring simultaneously in different cache memory is called cache coherence, or in some systems, global memory. In a multiprocessor system, consider that more than one processor has cached

2520-435: The main memory and one in the local cache of each processor that requested it. When one of the copies of data is changed, the other copies must reflect that change. Cache coherence is the discipline which ensures that the changes in the values of shared operands (data) are propagated throughout the system in a timely fashion. The following are the requirements for cache coherence: Theoretically, coherence can be performed at

2576-567: The nine-digit SBN code until 1974. ISO has appointed the International ISBN Agency as the registration authority for ISBN worldwide and the ISBN Standard is developed under the control of ISO Technical Committee 46/Subcommittee 9 TC 46/SC 9 . The ISO on-line facility only refers back to 1978. An SBN may be converted to an ISBN by prefixing the digit "0". For example, the second edition of Mr. J. G. Reeder Returns , published by Hodder in 1965, has "SBN 340 01381 8" , where "340" indicates

2632-502: The publication element. Once that block of ISBNs is used, the publisher may receive another block of ISBNs, with a different registrant element. Consequently, a publisher may have different allotted registrant elements. There also may be more than one registration group identifier used in a country. This might occur once all the registrant elements from a particular registration group have been allocated to publishers. By using variable block lengths, registration agencies are able to customise

2688-428: The publishing house and remain undetected, the book would be issued with an invalid ISBN. In contrast, it is possible for other types of error, such as two altered non-transposed digits, or three altered digits, to result in a valid ISBN (although it is still unlikely). Each of the first nine digits of the 10-digit ISBN—excluding the check digit itself—is multiplied by its (integer) weight, descending from 10 to 2, and

2744-508: The publishing industry is within a country. The first version of the ISBN identification format was devised in 1967, based upon the 9-digit Standard Book Numbering ( SBN ) created in 1966. The 10-digit ISBN format was developed by the International Organization for Standardization (ISO) and was published in 1970 as international standard ISO 2108 (any 9-digit SBN can be converted to a 10-digit ISBN by prefixing it with

2800-475: The ranges will vary depending on the number of books and the number, type, and size of publishers that are active. Some ISBN registration agencies are based in national libraries or within ministries of culture and thus may receive direct funding from the government to support their services. In other cases, the ISBN registration service is provided by organisations such as bibliographic data providers that are not government funded. A full directory of ISBN agencies

2856-465: The request and respond appropriately. Write propagation in snoopy protocols can be implemented by either of the following methods: If the protocol design states that whenever any copy of the shared data is changed, all the other copies must be "updated" to reflect the change, then it is a write-update protocol. If the design states that a write to a cached copy by any processor requires other processors to discard or invalidate their cached copies, then it

SECTION 50

#1732791084013

2912-405: The same book must each have a different ISBN assigned to it. The ISBN is thirteen digits long if assigned on or after 1 January 2007, and ten digits long if assigned before 2007. An International Standard Book Number consists of four parts (if it is a 10-digit ISBN) or five parts (for a 13-digit ISBN). Section 5 of the International ISBN Agency's official user manual describes the structure of

2968-415: The sum of all the thirteen digits, each multiplied by its (integer) weight, alternating between 1 and 3, is a multiple of 10 . As ISBN-13 is a subset of EAN-13 , the algorithm for calculating the check digit is exactly the same for both. Formally, using modular arithmetic , this is rendered: The calculation of an ISBN-13 check digit begins with the first twelve digits of the 13-digit ISBN (thus excluding

3024-430: The sum of these nine products found. The value of the check digit is simply the one number between 0 and 10 which, when added to this sum, means the total is a multiple of 11. For example, the check digit for an ISBN-10 of 0-306-40615- ? is calculated as follows: Adding 2 to 130 gives a multiple of 11 (because 132 = 12×11)—this is the only number between 0 and 10 which does so. Therefore, the check digit has to be 2, and

3080-545: Was by far the biggest user of the ISBN identifier in 2020, followed by the Republic of Korea (329,582), Germany (284,000), China (263,066), the UK (188,553) and Indonesia (144,793). Lifetime ISBNs registered in the United States are over 39 million as of 2020. A separate ISBN is assigned to each edition and variation (except reprintings) of a publication. For example, an ebook, audiobook , paperback, and hardcover edition of

3136-532: Was required to be compatible with the EAN format, and hence could not contain the letter 'X'. According to the 2001 edition of the International ISBN Agency's official user manual, the ISBN-10 check digit (which is the last digit of the 10-digit ISBN) must range from 0 to 10 (the symbol 'X' is used for 10), and must be such that the sum of the ten digits, each multiplied by its (integer) weight, descending from 10 to 1,

#12987