text:
US5339398A - Memory architecture and method of data organization optimized for hashing - Google Patents
Memory architecture and method of data organization optimized for hashing Download PDF
Imran A. Shah
Brian C. Johnson
Philips North America LLC
1989-07-31 Priority to US38827989A priority Critical
1991-08-19 Priority to US75022091A priority
1992-07-14 Application filed by Philips North America LLC filed Critical Philips North America LLC
G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
G06F16/90—Details of database functions independent of the retrieved data types
G06F16/901—Indexing; Data structures therefor; Storage structures
G06F16/9014—Indexing; Data structures therefor; Storage structures hash tables
A hashing data storage and retrieval arrangement whose storage capacity is unaffected by collisions. A first memory serves as a hash index table, for storing pointers at each address location corresponding to a hash value generated by hashing a key data word. Each pointer is the address of a location in a second memory, which has a separate storage location for each key data word, its associated data, and a further pointer which is the address of the next key data word resulting from a collision during hashing. Preferably a pipeline register between the two memories permits hashing of a subsequent key data word while accessing of the second memory is still in progress.
This is a continuation of application Ser. No. 07/750,220 filed Aug. 19, 1991 now abandoned which is a continuation of 07/388,279 filed Jul. 31, 1989, now abandoned.
CROSS-REFERENCE TO RELATED APPLICATIONS
The preferred embodiment disclosed herein embodies inventions claimed in four other concurrently filed commonly-owned applications, by one or both of applicants herein, namely Ser. Nos. 338,263; 388,281; 388,282; and 388,283.
The present invention relates to a memory architecture optimized for hashing, and to a method of organizing data which is optimized for hashing, and more particularly optimized for carrying out the Lempel-Ziv data compression algorithm.
The problem of organizing and storing data in a manner to allow quick retrieval is constantly encountered. A large variety of techniques known as hashing have been used to solve tile data organization and retrieval problem.
Frequently, a data element will have a value range that makes retrieval by searching by simple look-up impracticable. For example, a small five character ASCII word can have over a trillion possible values, and would require an equally large space of memory addresses if every possible value were allocated a unique address in the memory address space.
Hashing involves the application of a many-to-one function to the data element to map it from a larger to a smaller address space. The smaller address space will be the space of memory addresses in which the data is to be stored. A data element, called a key, is used as the argument of the many-to-one function, called the hash function. Storage of information associated with the key is accomplished by computing the hash function and storing the key, and associated data, in a memory at an address, called the hash address, corresponding to the hash function value. Because of the many-to-one property of the hash function, a smaller address space is required than if each of the possible data elements were to be assigned a unique address in memory. Retrieval of stored data associated with a particular key then involves simply computing the hash function value for the key and reading out the stored data from the memory.
Because of the many-to-one mapping by the hash function, more than one key can be hashed to the same memory address. This condition is called a collision, and a large number of techniques have been developed for resolving collisions. Good summaries of hashing techniques including collision resolution can be found in D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (1973) and J. S. Vitter, Analysis of Coalesced Hashing, Stanford University Department of Computer Science, Report No. STAN-CS-80-817, August 1980, reprinted in part at J. S. Vitter, "Tuning the Coalesced Hashing Method to Obtain Optimum Performance", Proceedings of Twenty-first Annual Symposium on Foundations of Computer Science, October 1980.
Many of the collision resolution methods utilize a technique called chaining. In the chaining method a dynamic linked list is maintained at each memory address corresponding to a hash function value or hash address. The hash addresses are stored in a table. The key and associated data is organized as a record which includes a key field, fields for data associated with the key, and a link field. After hashing a key, if there is a collision a sequential search is performed in the list to locate the particular record containing the key value being searched. If the list terminates without the key being found, and if it is desired to add the key and any associated data to the stored data, a new list element is added in the form of a record with that key as its content.
The chaining method has two principal advantages and two drawbacks. Because on the average the linked lists associated with each of the hash addresses are small, the search time for data retrieval is short. This remains true even as the hash address table begins to fill up. Knuth (cited above) has shown that even width the table completely full the chaining method requires only about 1.5 to 1.8 probes in order to locate the key. In addition, the hash address of the key is uniquely associated with it, that is, a key always hashes to the same hash value even though other keys may hash to that same value, and does not depend on the order in which the key is inserted in the hash address table. This uniqueness allows the use of abbreviated keys and a resultant reduction in storage requirements and in search time.
One possible problem with the chaining method is that the overhead of the link field could create severe memory requirements. A second problem is that an additional block of memory, used as overflow memory, is required in order to ensure adequate storage of the linked lists associated with each of the hash addresses. These two problems are intertwined.
If, because of the nature of the data, or because of Foot hash function properties, many keys are hashed to the same hash address, the overflow memory will have to be big enough to store a substantial part of the entire key space. Even for well behaved hash functions, Vitter (cited above) has shown that the overflow memory can increase the overall memory requirements from about 37% to 100%.
Hashing efficiency can be increased by expanding the memory available for hash addresses. The larger the hash table that can be used for a given number of entries, the less the likelihood of a collision. However, because each hash address requires an associated link field, increasing the memory available to the hash table will expand the memory requirements by more than just the additional memory allocated to the hash table.
It is accordingly an object of the invention to provide a memory architecture and a method of data organization optimized for hashing which permits collision resolution by chaining and which also minimizes the amount of memory which must be allocated.
According to the invention, the memory architecture optimized for hashing comprises two blocks of memory. The first block of memory is used only for storing link fields or pointers to the second block of memory. Each address in the first block of memory corresponds to a hash table address, and the pointer values stored in the first block of memory point to key values and associated data such as abbreviated keys or key portions, tag values, and/or further pointers, in the second memory block.
The disclosed architecture has several advantages. It inherently decouples the load factor of the hash table and the memory requirements for the keys and associated data. Secondly, the memory requirements of the second memory block can be met independent of the first memory block capacity. Moreover, no excessive memory requirements are created because of a poorly behaved hash function.
Each hash address in the first memory block stores only a single pointer. The capacity of the first memory block, and hence the hash table, can be expanded with minimum penalty because it does not contain the key or associated data. The second memory block need be only large enough to store key data, which by themselves or in conjunction with the address value are sufficient unambiguously to define the value which was hashed and is stored there, and other associated data. Even in the extreme case of a hash function hashing every key to the same hash address, the second block of memory need be no larger than that required by the data to be stored.
Another feature of the invention is that it can be readily implemented with a pipeline architecture which eliminates any penalty in system throughput arising from two successive access of the hash memory and the memory for the associated key and other data. This is achieved by the use of a register or other store between the first and second memories. This architecture allows a key to be hashed to an address in the first memory block and the stored pointer value to be read out and stored in the pipeline register. The pointer value in the register is subsequently used to read out the associated key data from the second memory block. During the time interval that the second memory block is being accessed, a subsequent key can be hashed to the first memory block, and consequently the hashing of the subsequent key is substantially eliminated from the total search time. As a result, throughput is as high as if only a single access were required.
BRIEF DESCRIPTION OF THE DRAWING
FIG. 1 illustrates tile data organization used in the present invention;
FIG. 2 illustrates the memory architecture according to the invention;
FIG. 3 illustrates another memory architecture according to the invention;
FIG. 4 illustrates a data compressor-decompressor having the memory architecture shown in FIG. 3;
FIG. 4A is a flow chart illustrating the operation of the data compressor-decompressor of FIG. 4;
FIG. 5 illustrates a data encoder used in the compressor-decompressor shown in FIG. 4;
FIG. 6 illustrates a decoder used in the compressor-decompressor shown in FIG. 4;
FIG. 7 is a schematic of the hash circuit shown in FIG. 4;
FIG. 8 is a schematic of one of the modulo-two adders shown in FIG. 7;
FIGS. 9 and 10 are schematics of other embodiments of hash circuits;
FIG. 11 illustrates a last-in first-out buffer comprising part of the control of the encoder shown in FIG. 5;
FIG. 12 is a block diagram of a data repacker 14 shown in FIG. 4.
The data organization or data structure used is illustrated in FIG. 1. A link field 1a is stored in memory independently of other data 2c at an address corresponding to a hash function value. Multiple link fields are stored in memory in a table at addresses corresponding to hash table values, and the value stored in the link field 2b at a hash table address is a pointer to the memory location of address of a corresponding key 2a and any other associated data fields 2c. Each key 2a is contained in a record 2 which also has an associated link field 2b for storing a pointer to a record of a successive key corresponding to the same hash address.
The corresponding memory architecture is shown in FIG. 2 and comprises a first memory 1 and a second memory 2. The first memory 1 stores only the link field values at the addresses comprising the hash table. Each address of the memory 1 is a hash table address and is addressed by a hash function value applied to the memory 1. In accordance with the invention, the capacity of memory 1 is chosen to optimize hashing according to a desired criteria. The load factor of the memory 1 used to store the hash table can be predetermined, and the capacity of memory 1 selected to achieve that load factor.
It is evident that the capacity of memory 1 and its load factor can be selected solely according to the size of the hash table, if desired. There is no need to consider the number of key fields or other data fields that will be stored, in order to select the capacity of memory 1. Memory 2 is used to store the key and other data fields.
Data stored in memory 2 can be inserted successively, and the address values at which the keys and other data are stored are the pointer values in the memory 1. The capacity of memory 2 is selected to be sufficient to meet the storage requirements for the keys and other data. The link fields in memory 2 permits chaining to be used for collision resolution. The first key corresponding to a particular hash address that is inserted in the memory 2 has an address in memory 2 corresponding to the pointer stored in memory 1 at the hash address. The second key corresponding to the same hash address is stored in memory 2 at an address of memory 2 which is stored in the link field of the record containing the first key. In this way, a linked list is created within memory 2 that is accessed through the pointer value stored in memory 1. The keys and other data successively stored in memory 2 can be stored in contiguous memory in the form of linked lists to maximize utilization of memory 2. The capacity of memory 2 need only be sufficient to meet the storage requirements of the data. Thus, the capacity of each memory can be independently optimized for hashing.
A consequence of the decoupling of the hash addresses and the associated key and other associated data fields is that a minimum of two memory accesses is required in order retrieve a key. This doubling of retrieval time for a single key might be acceptable if retrieval of stored data is infrequent. However, if the stored data must be accessed repeatedly it would be desirable to effectively eliminate, or at least greatly reduce, the increased access time of the memory architecture just described.
FIG. 3 illustrates another memory embodiment comprised of a first memory 3 for storing the link fields comprising the hash table. A second memory 4 stores key and other associated data fields, and link fields associated with each key, in the manner already described. Thus, both embodiments use the same method of data organization. This second embodiment further comprises a register 5 for storing the pointer values read out from the first memory 3, and for using the pointer values stored therein to access the second memory 4. The storage of the pointer value read out from the first memory 3 within the register 5 permits a second key to be hashed to the first memory 3 while the second memory 4 is being accessed.
For example, suppose a key ki is hashed to a particular address in the first memory 3 and a pointer stored at that address is read out. At the next read operation a subsequent key ki+1 will be hashed to another address of the memory 3, while the pointer value in the register 5 will address the memory 4 to read out the data associated with ki. The system can perform a validity test of the data stored in memory 4, that is, look for a match of key ki with the content of memory 4, while the key ki+1 is being hashed to the first memory 3. If a match with key ki is attained the pointer associated with key ki+1 can be applied to the second memory 4; otherwise, nothing is done with the pointer corresponding to key ki+1 until key ki is resolved as either a success or failure. In either event, the access of the first memory 3 by the hashed value of key ki+1 will have already occurred and will not contribute to the total search time.
One application for the disclosed data structure and memory architecture is in the area of data compression. FIG. 4 illustrates the structure of a dedicated integrated circuit for carrying out data compression according to the Lempel-Ziv algorithm, in which hashing is carried out by hardware circuits. The data which is hashed is organized and stored in a memory as just described.
A good introductory explanation of the Lempel-Ziv (LZ) algorithm can be found in the article by Terry A. Welch, "A Technique for High-Performance Data Compression", Computer, June 1984, pp. 8-19. The treatment of the algorithm given in the Welch article is summarized below.
The LZ algorithm maps strings of input characters into fixed-length codes. The string-code word pairs are stored in a table called the string table. Table entries are generated during data compression. More particularly, a message comprised of a sequence of characters is parsed character-serially in one pass, and the longest recognized input string S is parsed off each time. A recognized string is one that already exists in the string table. The code word for the recognized string S is transmitted, and the recognized string S with the next character C of the message appended, SC, is added to the string table and assigned a unique code word.
The LZ algorithm can be more explicitly described as follows:
______________________________________Initialize string table to contain single-character    strings of message charactersRead first input character → prefix string SSTEP: Read next input character C    If no such C (input exhausted): code S → output; EXIT    If SC exists in string table: SC → S; repeat STEP    Else SC not in string table: code (S) → output       SC → string table        C → S; repeat STEP______________________________________
Starting with an initialized string table containing the character set from which the message will be composed, the first message character is read and set to the prefix string S. If there is a subsequent message character it is read and appended to the prefix string to form the new string SC. The string table is then checked to determine whether the string SC is already entered. If there already is an entry for SC, then the string SC is set to the prefix string S, the next message character C is read, and the step is repeated. Otherwise, if the string SC is not in the table, the output code word for the prefix string S is transmitted, a new table entry for the string SC is created, the character C is set to the prefix string S, and the step is repeated.
The data compressor/decompressor is comprised of a first-in first-out buffer memory (FIFO) 10 having an input which constitutes a data port which receives the sequence of message characters to be compressed. The FIFO 10 is not an essential element of the system but is used to smooth the data rate which could otherwise vary because of the variable search times that can occur during execution of the LZ algorithm.
A coder/decoder (CODEC) 12 receives the output from the FIFO 10 and encodes the applied signal according to the LZ algorithm by operating in the encoding mode. The encoded signals from the CODEC 12 are applied to repacker 14 which accepts input data streams of variable width and which generates output data streams of variable width, The repacker 14 output is applied to the FIFO 16 which is effective to smooth the rate of the code signals sent from the code port of the data compressor/decompressor.
The FIFO's 10 and 16, the CODEC 12, and the repacker 14 are initialized and put in operation by the microprocessor/memory interface 18. The interface 18 receives control signals from the system in which the data compressor/decompressor is incorporated, and passes signals between the components of the data compressor/decompressor just described and memories used by it. The FIFO's 10 and 16, CODEC 12, repacker 14 and interface 18 are, in the preferred embodiment, fabricated as a single integrated circuit, as shown by the dashed line in FIG. 4. The memories 20, 21 and 22, which are described below, are separate components. Alternatively, some or all of the components of the data compressor/decompressor could be constructed as separate units, or memory could be provided on the integrated circuit comprising the data compressor/decompressor.
The memory architecture requires that the Lempel-Ziv algorithm be executed somewhat differently than the basic LZ algorithm described above. This is because the first memory (21 in FIG. 4) contains only pointer values and thus can not be addressed without a string including a prefix, and the correct value of the string prefix will not be known with certainty without accessing and resolving the search in the second memory (22 in FIG. 4).
In order to use the pipelined memory architecture the LZ algorithm is executed by selecting a prefix. As will be more fully explained below, the selected prefix is either an assumed prefix which is a codeword corresponding to the pointer (address in the second memory) resulting from the immediately previous hashing, when that second memory address had already contained certain data; or is the immediately preceding character. The selected prefix and the latest received character (data) are concatenated to form a prefixdata combination which is then hashed to provide an address in the first memory 21. The first memory is accessed to determine if a resulting pointer value is already stored there. If a resulting pointer value is stored in the first memory 21, thus indicating that the second memory 22 includes data at this address, a success is assumed.
Accordingly, that resulting pointer value becomes the next assumed prefix, and it and the next received data are hashed to the first memory 21 while the resulting pointer value derived from the previous hashing operation is used to address the second memory 22. If there is a match between the two keys (for example, an abbreviated key stored at that location in the second memory 22 and an abbreviated key obtained from the hashing whose success had been assumed) one cycle of the processing of the next-prefix data will have been achieved. On the other hand, if the key does not match, i.e. there is a failure, the assumption about the prefix was incorrect. In the next cycle the key will be written in the second memory, and also during that cycle the new key with the corrected prefix will be hashed to the first memory. In this way the speed increase attributable to a pipeline architecture can be achieved with the LZ algorithm.
The justification of anticipating the prefix value is a consequence of the fact that the LZ algorithm compresses data such as an image by a factor of two to three, with average string lengths of between four and six data elements. This results in success about three times more frequently than failure when searching for a prefix-data combination. Consequently, one can anticipate a prefix and be correct 75% of the time, even before a prefix can actually be resolved.
In LZ encoding, data strings of varying length are represented by codes. Each successive data word is appended to a prefix, which is a code representing a string of previous data words. A search is then performed in the code-table for this prefix-data combination, representing a longer string. If the prefix-data combination is found in the code table ("a success") the code assigned to this prefix-data combination becomes the new prefix. The next data word will then be appended to this new prefix when the cycle is repeated. If the prefix-data combination is not found in the code table, it is added to the table along with a new code-word representing it. The prefix, representing the longest found data string found in the table, is transmitted.
The CODEC 12 includes circuitry for both encoding input data according to the LZ algorithm, and for decoding LZ-encoded data.
The encoder portion of the CODEC 12 is illustrated in FIG. 5. A new data word is received from the FIFO 10 by the data register 32. A prefix register 33 stores a prefix to which the new data word is to be appended. The new data word and the prefix from the register 33 are applied to a hash circuit 34 which develops a hash address and an abbreviated key. The hash circuit 34 is described in detail, below.
The hash address is applied through the signal path 35 to the hash-tag memory 20, 21 to read out the content of the memory 20, 21 at the address corresponding to the hash function. The tag value read out from the hash-tag memory is either 0 or 1 depending upon certain conditions. The memory 21 reads out a pointer to the possible location of the key in the second memory. (Although hash-tag memory 20, 21 is shown in FIG. 5 as part of the encoder, it is physically separate from the encoder as shown in FIG. 4)
A tag bit value of 0 indicates that the prefix-data combination has not been encountered before (a "failure"). In this case a new code word corresponding to the hash address is obtained from the code-word-counter 37 and entered at the memory location of the hash memory 21 through the encoder control 36. The tag bit is re-written as a 1 to indicate a valid entry at the memory location. Finally, the abbreviated key is entered at the code-word location of the key-code-word memory 22. The prefix-multiplexer 40 selects the current data from the register 32 as the next prefix and stores it the prefix-register 33. The current prefix content of the register 33 is transmitted out through the transmit multiplexer 45 to the repacker 14.
A tag bit value 1 indicates a valid entry in the hash memory 21. In this case, the content of the hash memory will be used in the next cycle as an address to read and compare the abbreviated key. At the same time the prefix multiplexer will assume that the abbreviated key will match and will use the contents of the hash memory 21 as the next prefix. If the abbreviated key matches, i.e., a success, the prefix assumption was valid. The operation of the encoder continues using the results of the access to the hash-memory.
If the abbreviated key does not match and the tag bit of the key-code word memory 22 is 0, which indicates an end of list, then the condition is a failure following a collision. The assumption made about the prefix in order to carry out the hash operation was incorrect. The results of the hash operation are then ignored and the old data stored in the old data register 41 is used as the new and correct prefix. At the same time the old prefix stored in the register 42 is transmitted out. The tag bit value of the key/code-word memory is updated to 1, and the code word value is written in the code-word memory 22. In the next cycle, using the code word memory contents as the address, the new abbreviated key is written in the key memory 22 and the tag bit at that location is initialized to 0. In other words, a new link is added to the link list, and the end-of-list pointer is updated.
When the abbreviated key does not match, but the tag bit of the key/code-word memory is 1, the end of the list has not yet been reached. The content of the code-word memory 22 at this address is pointing to the next possible location of the key being sought.
In the next cycle the content of the code-word memory is used as an address and the key is searched for again. This process is continued until either the key is found, a success occurs, the end-of-list is reached, or a failure occurs. Each time an address is found pointing to the next possible location of the key, it is assumed that the key is going to be found there. Because a success is assumed, this address is used as the prefix for hashing and is passed through the prefix multiplexer 40 to the hash circuit 34. The results of a hashing are used only if the key matches, i.e. a success occurs.
Information regarding the data to code word correspondence developed by the encoder during the encoding process is used by the decoder during subsequent decoding. During encoding a transmission is made after every failure, and is accompanied by a new code-table entry. This information is used by the decoder. Each time the decoder receives a code it makes a corresponding entry to its code-table by appending the first character of the currently received code to the previous code and assigning a new code word to it in the code table. At the same time the decoder outputs a string corresponding to the current code, always operating just a step behind the encoder.
The decoder circuit of the CODEC 12 is shown in FIG. 6. Current code word register 51 receives a code word from the repacker 14. The register 51 receives a code word after a previous code word has been decoded so that the code word stored in the register 51 is the current code word to be decoded. The code word stored in the register 51 is also stored in the register 52 for use as the previous code word after the register 51 receives a new code word. Finally, the current code word is tested by the circuit 53 to determine whether it is "Special" as described later.
The multiplexer 54 applies the current code word to the comparator 55 which checks whether the code word belongs to the "Basic" set or is a "Special" case. If the code word is not Basic and not Special the multiplexer 56 passes it to address register 56a to be used as an address for retrieving the data-code word entry at that address in the data memory 57 and code word memory 58. The data at that address is transmitted through the multiplexer 59 to the LIFO control logic 138. Similarly, the code word retrieved from that address is used again, and is transmitted through multiplexer 54 to the comparator 55 to determine whether it is Basic. This sequence of steps is repeated until the code word retrieved from the code word memory 58 is Basic.
If the code word is determined to be Basic, the end-of-string condition has been reached. The end-of-string condition occurs when the decoder has completed unraveling the string represented by the current code word. The register 55a provides a one-clock-pulse delay in the control signals consistent with the pipeline operation of the decoder. At this time the decoder is ready to make a new entry in the decoder table at the memory address pointed to by the next-entry counter 60 through the next entry latch 60a and the multiplexer 56. The decoder is also ready to accept a new code word from the current-code-word register 51. In the next cycle of operation the Basic code word is output from the register 61 through the multiplexer 59. At the same time a new entry comprising the previously received code word stored in the register 52, and the first character of the current code word, stored in register 61, is written into the code word memory 58 and data memory 57, respectively. A new code word is also taken from the current code word register 51 at this time.
A code word is considered Special if it is also the next entry to be made in tile decoder table. The new code word is compared by the Special comparator 53 with the count value of the next entry counter 60. If the new code word and the next entry counter value match the code word is Special. The Special condition latch 53a provides a clock delay required by the pipelining of the decoder. Because no entry corresponding to this code word has been made in the decoder tables, the data memory 57 and the code word memory 58 will not be accessed in the following cycle of operation. Instead, the first character of the previous code word, stored in the register 62 is transmitted to the LIFO 10 through the multiplexer 59. To continue the decoding the previously received code word from the register 52 is passed through the second previous code word register 52a which functions as a pipeline delay latch to the multiplexer 54 and used as the address to access the data memory 57 and the code word memory 58.
The scheme for generating the hash function is implemented by a special purpose circuit. Before describing the hash function generating circuit the mathematical functions governing the hash function will be considered.
The design of hash function generators has received considerable attention. The hash function generator must efficiently generate the hash function from the key, and it must perform a pseudo-randomizing function so that all of the keys are not mapped into the same hash address.
For example, a small five-character ASCII field would require (128)5 or over one trillion memory address, if it were to be stored in unique addresses corresponding to its value. The first character of the five character field might be taken as a simple hash function thereby reducing the address field of the hash function to only 128 locations. To retrieve a data item of interest one would address the memory location corresponding to the value of the first character of the key, and then look for the entry with the key that matches all five characters. Obviously, if every key started with the same character, then the desired key and data could be retrieved only by searching the entire address space of the keys.
It should also be noted that in the given example, all keys corresponding to a particular hash function have the same first character. Thus, in such a case the first character of the keys need not be stored, and an abbreviated key can be used instead. In this example the abbreviated key would be the last four letters of the word. Accordingly, it would be desirable to use a hash function generator that is efficient, is pseudo-randomizing and which permits the use of abbreviated keys. This last property imposes the requirement that the hash function and the abbreviated key uniquely represent the input key.
According to the method that is employed, the key k, hash function h and abbreviated key a, are represented in binary form as vectors. The hash function generator H and abbreviated key generator A are matrices of 1's and 0's which satisfy the following equations,
h=Hk                                                       (1),
a=Ak                                                       (2).
Equations (1) and (2) can be combined in the following manner ##STR1## where ##STR2## is a vector, and ##STR3## is a matrix. If the matrix ##STR4## is invertible, then the following relation holds ##STR5## Consequently, the combination of the hash function h and the abbreviated key a uniquely represent the original key k. This is an important feature. The uniqueness of the combination of the hash function and the abbreviated key allows for the storage of just the abbreviated key in the second memory with an attendant reduction in memory requirements, and without the loss of the ability to resolve collisions.
The form of the hash function generator H, and the operations required to compute equation (1), are particularly well suited to hardware implementation. This can be seen by expanding equation (1) to show the individual elements of the matrix H and vector k as follows: ##STR6## The hash function generator H is an m×n matrix, where hij=0 or 1. The key k is a column vector of n bits, and ki =0 or 1. Carrying out the matrix multiplication yields: ##STR7## which is an m×1 column vector. Each element of the hash function h is calculated as the sum
h.sub.i =Σh.sub.ij k.sub.j, j=1 . . . n              (7)
where the multiplications are binary multiplications, or logical AND, and the summation is binary addition without carry, or modulo-two addition. Thus, the products hij kj =1 or 0 depending upon whether hij is 1 or 0, and signals corresponding to the products hij kj can be obtained by simply transmitting or not transmitting the bit kj depending upon whether hij is 1 or zero. The ith bit, hi, of the hash function h is then equal to the modulo-two sum of the transmitted kj values for that particular value of i.
For example, assume the following hash function generator: ##STR8## which is a (3×6) matrix for generating a three-bit hash function from a six-bit key.
A hashing circuit which implements this generator and carries out hashing using it is shown in FIG. 7. The hashing circuit is comprised of n signal lines each corresponding to a column of the hash function generator H. The key k is represented by binary signals k1 through k6, and each is applied to a corresponding one of the signal lines 64, 65, 66 etc. The modulo-two adders 67, 68 and 69 with their input connections each correspond to a row of the hash function generator H, and each develops a binary output signal corresponding to one of the three bits of the hash function h.
The connections between the signal lines 64 etc. and the inputs of the modulo-two adders 67-69 correspond to the non-zero elements of the hash function generator H. For example, modulo-two adder 67 corresponds to the first row of the matrix H, which has 1 in the first, third and sixth columns. Signal line 70 connects the signal line for k1 to the modulo-two adder 67, and similarly signal line 71 connects the signal line for k3 and signal line 72 connects the signal line for k6 to it. The output of adder 67 is then (k1 +k3 +k6) (mod 2)=h1.
Similarly, the modulo-two adders 68 and 69 develop binary output signals corresponding to the bits h2 and h3 of the hash function h. In the case where an abbreviated key is to be generated, additional modulo-two adders are provided for the respective bits of the abbreviated key.
The modulo-two adders can be constructed by connecting Exclusive-OR gates 67a and 67b in the manner shown in FIG. 8. This circuit is also known as a parity checker and can be readily expanded by adding more Exclusive-OR gates in order to accommodate more than three inputs.
An advantage of the disclosed hashing circuit is that hashing can be carried out at the system clock speed. Unlike other hashing techniques which use other types of hash function generators, the matrix multiplication of equation (1) is carried out in a single step with the simultaneous occurrence of the multiplications and additions comprising the matrix multiplication. Thus, the circuit can be readily used for carrying out hashing in real time.
Another advantage of the hashing circuit is that it can be made programmable, and a particular hash function generator H can be selected after the circuit has been fabricated. A programmable embodiment of the hashing circuit is shown in FIG. 9. This circuit comprises n input signal lines 81, 82, 83, etc. each for receiving a corresponding one of the binary signals k1 through kn corresponding to the bits of the key. There are m modulo-two counters, the first of which are labeled 89 and 89m. The output of each modulo-two counter is a binary signal corresponding to one bit of the hash function h.
Each modulo-two counter has n inputs, and n circuit paths 91, 92, etc, are connected to the respective inputs. The signal lines 81, 82 . . . and the circuit paths 91, 92 . . . cross in an array to permit interconnections between the two. The interconnections between the signal lines and the circuit paths are made by diodes 100, 101, etc. Each diode is connected between a respective one of the signal lines and a respective one of the circuit paths. For example; diode 100 connects signal path 81 and circuit path 91; diode 101 connects signal path 82 and circuit path 92, etc. The diodes are fusible in order to open the connection which they establish. Upon the application of a sufficiently high voltage to a selected one of the diodes, the selected diode fails and an open circuit exists between the signal line and the circuit path between which it was connected. The use of fusible diodes to open predefined circuit links and thereby render a circuit programmable is known from programmable logic device technology and can be done in the manner known in that technology.
For simplicity, not all of the signal lines, circuit paths or diodes are shown. As the programmable hash circuit has been described, however, there are n circuit paths for each of the m modulo-two adders, and a diode for connecting each of the signal lines to a corresponding circuit path. This structure is programmable to realize any m-bit hash function, but the modulo-two adders are consequently of the maximum size.
In another embodiment of the invention the modulo-two adders have fewer inputs than the number of signal lines, and at some of the circuit paths is connected to more than one signal line. Such an embodiment is shown in FIG. 10 in which the modulo-two adders 120, 121 and 122 have fewer than n inputs. In this particular embodiment, the modulo-two adders 120 and 121 have an equal number of inputs and the modulo-two adder 122 has a fewer number of inputs. Different schemes for allocating diode connections between the signal lines and the circuit paths can be used. The modulo-two adders 120 and 121 have a sufficient number of diodes 110, 111 etc. so that each signal line is connected to at least one circuit path. In contrast, every signal line is connected to every circuit path for the modulo-two adder 122 so as to achieve the maximum degree of programmability.
The matrix which is a composite of the hash function generator H and the abbreviated key generator A can be derived in a straightforward manner. Starting with the identity matrix pairs of bit rows or columns can be selected at random, added modulo-two, and the sum substituted for the first selected row or column, or simply exchanged. These linear operations applied to an invertible matrix preserves the invertibility property. Consequently, it provides a way to generate a randomized invertible matrix. These steps must be repeated any number of times, and the first m rows of the resulting matrix is H and the remaining (n-m) rows is A.
To reverse the order of characters in the string sequence as the LZ decoding algorithm requires, the data decoder applies its output to a last-in first-out buffer (LIFO), which is illustrated in FIG. 11. The LIFO is comprised of two random access memories (RAM) 130 and 131, controlled by LIFO control logic 138, through which input data from CODEC 12 and output data pass. A first character string is read into the memory 130. The character order is preserved by the address counter 132 which develops a sequence of address values for storing the characters of the input string in sequence.
Diminishment of the system performance by LIFO operation is avoided by the provision of a second RAM 131 which can also be addressed during addressing of the RAM 130. Character strings are stored in order in the RAM 131 under control of its corresponding address counter 133.
To prevent loss of data an overflow memory 135 is provided to receive and store data when the respective RAM 130 or 131 being written into is full. For example, if an input string is written into RAM 130 and its capacity is reached, the input string is then written into the overflow memory 135. The order of the string is preserved by using the address counter 132 for both the RAM 130 and the overflow RAM 135. When the RAM 130 becomes full additional data is passed to the overflow RAM 135 and the address counter 132 continues the sequential count of address values associated with the string being read in. The address values are applied through the address multiplexer 136 so that correspondence between the string characters and the count value is preserved even though the string is stored in two physically separate memories.
When the string data is read out the address counter 132 counts backward from the last memory value address during the writing of the string into the overflow RAM 135. In this way the stored string i s read out in reverse order.
During the reading out of the string stored in the overflow RAM 135 and RAM 130, another string is written into the RAM 131 and stored at successive memory locations having addresses determined by the address counter 133. The feature of separate means for developing address values for the respective memories 130, 131 enables them to be operated separately so that one can write in data while data is read out from the other. In this way equal length strings can be reversed without slowing the processing speed of the system in which the LIFO buffer is used.
From the described mode of operation it is clear that for RAMS 130 and 131 having at least a depth D, the LIFO buffer can continuously buffer strings of length 2D without any loss of speed. This result follows from the fact that a stored string of length 2D filling one RAM, for example RAM 130, and the overflow RAM 135 is read out first from the overflow RAM 135 in order to reverse the string. During this reading out the simultaneous writing and storage of a subsequent string will start with the RAM 131. The RAM 131 of depth D will not be completely filled until the overflow RAM 135, which stored a string segment of length D, is empty thus freeing the overflow RAM 135 to store the remaining segment of length D of the string being written.
In order to handle strings of length greater than 2D the overflow RAM 135 must have a depth greater than D. Strings longer than 2D will degrade the performance of the LIFO buffer. The degree of performance degradation is equal to the sum of the long string length and the short string length divided by twice the long string length. In the worst case the LIFO buffer speed approaches one-half the maximum speed.
The data repacker 14 circuit is shown in FIG. 12. It is comprised of an input data register 140 and an output data latch 141, both of which help improve system performance. Neither the register 140 or the latch 141 are used in the actual data repacking function, however.
The holding register 142 is used to store intermediate results and has a storage length twice the size of the data words being repacked. Shifter 143 and shifter 144 also have a storage length twice the size of the data words and select a number of bits equal to the data word length, e.g. sixteen of thirty-two bits. The multiplexer 145 is a 2:1 multiplexer. One input of the multiplexer 145 is connected to the output of the holding register 142, to maintain the contents of register 142 until the amount of valid data remaining leaves room for concatenation of new data latched in register 140. When directed by the control circuit 146, the other input receives concatenated input data and data from shifter 143.
In operation, the control circuit 146 receives signals from the microprocessor/memory interface 18 which represent the number of bits in (NBI) and the number of bits out (NBO). From this information it determines a most significant bit (MSB) and a least significant bit (LSB) of the intermediate data which will be stored in the holding register 142.
When data is passed to the input of the repacker it is latched by the input data register 140, and on the next clock cycle it is combined with the intermediate data in the holding register 142, if there is room. There will be room if there are fewer valid intermediate data bits in the holding register 142 than the number of bits in a data word. The number of valid data bits equals MSB minus LSB. If there is sufficient room the input data becomes the high bits of the holding register, and the shifted data from the holding register becomes the low bits of the holding register. If there is insufficient room in the holding register 142 the input data is not combined with the intermediate data. The shifter 144 receives a signal indicating the LSB and shifts its content to the right-justify the intermediate data for presentation at the output.
1. A method of pipe-lined memory accessing for a multiplicity of sequentially received data values forming a string, comprising:
receiving said sequentially received data values,
storing pointer values in a first memory,
storing data values and respective further pointer values in a second memory at locations corresponding to pointer values in said first memory,
hashing respective prefix-data combinations formed from a respective prefix and a respective one of said data values to provide a respective hash value, said respective hash value including an address in said first memory,
responsive to hashing of a given prefix-data combination including a given received data value, and the resulting hash value corresponding to one location in said first memory at which a pointer value is already stored, hashing the next received data value with an assumed prefix having a value corresponding to that already stored pointer value; comparing the data value stored at the location corresponding to said pointer value stored at said one location in said second memory with a value related to said given received data value, while hashing said assumed prefix with said next received data value; and selecting the prefix for the next hashing responsive to the result of the comparison, and
responsive to hashing of said given prefix-data combination including said given received data value, and the resulting hash value corresponding to a location in said first memory at which a pointer value is not already stored, hashing the next received data value with a prefix having a value corresponding to said given received data value.
2. A method as claimed in claim 1, characterized by storing, at each location in said first memory, a respective tag bit whose value indicates whether or not a respective said pointer value is stored at that location.
3. A method as claimed in claim 1, characterized by storing, at each location in said second memory, a respective tag bit whose value indicates whether or not a respective said data value is stored at that location.
4. A method as claimed in claim 1, characterized in that said hashing produces hash values which respectively comprise an address portion and an abbreviated key, said address portion and abbreviated key together being invertible,
said data values stored in said second memory comprise said abbreviated keys, and
comparing includes comparing the respective abbreviated key stored in the second memory with the abbreviated key portion of the hashed value of the corresponding received data value.
5. An apparatus for pipe-lined memory accessing for a multiplicity of sequentially received data values forming a string, comprising:
means for receiving said sequentially received data values,
a first memory for storing pointer values,
a second memory for storing data values and respective further pointer values at locations corresponding to pointer values in said first memory,
comparing means for comparing the data value stored in a given location in said second memory with a value related to one of said received data values,
means for selecting a prefix, and
hashing means, coupled to the means for receiving and said means for selecting, for hashing respective prefix-data combinations formed from a respective prefix and a respective one of said data values to provide a respective hash value, said respective hash value including an address in said first memory,
said means for selecting, responsive to hashing of a given prefix-data combination including a given received data value, and the resulting hash value corresponding to one location in said first memory at which a pointer value is already stored, providing a value corresponding to that already stored pointer value to said hashing means, to be an assumed prefix for hashing with the next received data value after said given received data value; said comparing means, while said hashing means is then hashing said assumed prefix with said next received data value, comparing the data value stored at the location corresponding to said pointer value stored at said one location in said second memory with a value related to said given received data value; and said means for selecting being responsive to the result of the comparison in selecting the prefix for the next hashing, and
said means for selecting, responsive to hashing of said given prefix-data combination including said given received data value, and the resulting hash value corresponding to a location in said first memory at which a pointer value is not already stored, providing said given received data value to said hashing means to be the prefix for hashing with the next received data value after said given received data value.
6. An apparatus as claimed in claim 5, characterized in that said first memory comprises, at each location, a respective tag bit whose value indicates whether or not a respective said pointer value is stored at that location.
7. An apparatus as claimed in claim 5, characterized in that said second memory comprises, at each location, a respective tag bit whose value indicates whether or not a respective said data value is stored at that location.
8. An apparatus as claimed in claim 5, characterized in that said hashing means produces hash values which respectively comprise an address portion and an abbreviated key, said address portion and abbreviated key together being invertible,
said means for comparing compares the respective abbreviated key stored in said given location with the abbreviated key portion of the hashed value of said one of said received data values.
US07/913,764 1989-07-31 1992-07-14 Memory architecture and method of data organization optimized for hashing Expired - Fee Related US5339398A (en)
US38827989A true 1989-07-31 1989-07-31
US07/913,764 US5339398A (en) 1989-07-31 1992-07-14 Memory architecture and method of data organization optimized for hashing
US75022091A Continuation 1991-08-19 1991-08-19
US07/913,764 Expired - Fee Related US5339398A (en) 1989-07-31 1992-07-14 Memory architecture and method of data organization optimized for hashing
US6052697A (en) * 1996-12-23 2000-04-18 Microsoft Corporation Reorganization of collisions in a hash bucket of a hash table to improve system performance
US6115802A (en) * 1995-10-13 2000-09-05 Sun Mircrosystems, Inc. Efficient hash table for use in multi-threaded environments
WO2001029671A1 (en) * 1999-10-15 2001-04-26 Neo-Core, L.L.C. Memory management system and method
US6243720B1 (en) * 1998-07-08 2001-06-05 Nortel Networks Limited Address translation method and system having a forwarding table data structure
US6275919B1 (en) * 1998-10-15 2001-08-14 Creative Technology Ltd. Memory storage and retrieval with multiple hashing functions
US6308246B1 (en) * 1997-09-05 2001-10-23 Sun Microsystems, Inc. Skewed finite hashing function
US20020032691A1 (en) * 2000-05-26 2002-03-14 Infolibria, Inc. High performance efficient subsystem for data object storage
US6434662B1 (en) * 1999-11-02 2002-08-13 Juniper Networks, Inc. System and method for searching an associative memory utilizing first and second hash functions
US6442553B1 (en) * 1994-10-31 2002-08-27 Fujitsu Limited Hash system and hash method for transforming records to be hashed
US6535867B1 (en) * 1999-09-29 2003-03-18 Christopher J. F. Waters System and method for accessing external memory using hash functions in a resource limited device
US6633999B1 (en) * 1999-12-03 2003-10-14 Macronix International Co., Ltd. Integrated circuit with on-chip data checking resources
US20030233514A1 (en) * 2002-06-14 2003-12-18 Integrated Device Technology, Inc. Use of hashed content addressable memory (CAM) to accelerate content-aware searches
US20030233515A1 (en) * 2002-06-14 2003-12-18 Integrated Device Technology, Inc. Hardware hashing of an input of a content addressable memory (CAM) to emulate a wider CAM
WO2005010773A1 (en) * 2003-07-23 2005-02-03 Intel Corporation Method and system for high-performance hashing
US20050071386A1 (en) * 2003-09-25 2005-03-31 International Business Machines Corporation Method, system, and program for data synchronizatiom
US20050120336A1 (en) * 2003-11-28 2005-06-02 International Business Machines Corporation System and method for performance monitoring
US20050195743A1 (en) * 2000-04-03 2005-09-08 P-Cube Ltd. Real time charging of pre-paid accounts
US20050283711A1 (en) * 2004-05-13 2005-12-22 Claseman George R Look-up table expansion method
US20060095654A1 (en) * 2004-11-02 2006-05-04 Integrated Device Technology, Inc. Fast collision detection for a hashed content addressable memory (CAM) using a random access memory
EP1672488A2 (en) * 2004-12-14 2006-06-21 Axiomatic Solutions SDN.BHD. Compile time linking via hashing technique
US20060271539A1 (en) * 2005-05-27 2006-11-30 International Business Machines Corporation File storage method and apparatus
US20080244212A1 (en) * 2007-03-29 2008-10-02 Rothman Michael A System and method to enable hierarchical data spilling
US20100082562A1 (en) * 2008-03-05 2010-04-01 Vinay Deolalikar Managing Storage Of Data In A Data Structure
US20100274786A1 (en) * 2009-04-22 2010-10-28 Brightcloud Inc. System And Method For Performing Longest Common Prefix Strings Searches
US20110029480A1 (en) * 2009-08-03 2011-02-03 IntelliCubes, Inc. Method of Compiling Multiple Data Sources into One Dataset
US7996520B2 (en) 2007-09-19 2011-08-09 Cisco Technology, Inc. Behavioral classification of communication sessions using active session initiation
US20120278651A1 (en) * 2011-04-28 2012-11-01 Naveen Muralimanohar Remapping data with pointer
US8775776B2 (en) 2012-01-18 2014-07-08 International Business Machines Corporation Hash table using hash table banks
US8924741B2 (en) 2012-12-29 2014-12-30 Intel Corporation Instruction and logic to provide SIMD secure hashing round slice functionality
US20150046683A1 (en) * 2013-03-15 2015-02-12 Soft Machines, Inc. Method for using register templates to track interdependencies among blocks of instructions
US9027104B2 (en) 2012-12-28 2015-05-05 Intel Corporation Instructions processors, methods, and systems to process secure hash algorithms
US9766893B2 (en) 2011-03-25 2017-09-19 Intel Corporation Executing instruction sequence code blocks by using virtual cores instantiated by partitionable engines
US9811342B2 (en) 2013-03-15 2017-11-07 Intel Corporation Method for performing dual dispatch of blocks and half blocks
US9811377B2 (en) 2013-03-15 2017-11-07 Intel Corporation Method for executing multithreaded instructions grouped into blocks
US9823930B2 (en) 2013-03-15 2017-11-21 Intel Corporation Method for emulating a guest centralized flag architecture by using a native distributed flag architecture
US9842005B2 (en) 2011-03-25 2017-12-12 Intel Corporation Register file segments for supporting code block execution by using virtual cores instantiated by partitionable engines
US9858080B2 (en) 2013-03-15 2018-01-02 Intel Corporation Method for implementing a reduced size register view data structure in a microprocessor
US9886279B2 (en) 2013-03-15 2018-02-06 Intel Corporation Method for populating and instruction view data structure by using register template snapshots
US9886416B2 (en) 2006-04-12 2018-02-06 Intel Corporation Apparatus and method for processing an instruction matrix specifying parallel and dependent operations
US9898412B2 (en) 2013-03-15 2018-02-20 Intel Corporation Methods, systems and apparatus for predicting the way of a set associative cache
US9912481B2 (en) 2014-03-27 2018-03-06 Intel Corporation Method and apparatus for efficiently executing hash operations
US9921845B2 (en) 2011-03-25 2018-03-20 Intel Corporation Memory fragments for supporting code block execution by using virtual cores instantiated by partitionable engines
US9934042B2 (en) 2013-03-15 2018-04-03 Intel Corporation Method for dependency broadcasting through a block organized source view data structure
US9940134B2 (en) 2011-05-20 2018-04-10 Intel Corporation Decentralized allocation of resources and interconnect structures to support the execution of instruction sequences by a plurality of engines
US9965281B2 (en) 2006-11-14 2018-05-08 Intel Corporation Cache storing data fetched by address calculating load instruction with label used as associated name for consuming instruction to refer
US10031784B2 (en) 2011-05-20 2018-07-24 Intel Corporation Interconnect system to support the execution of instruction sequences by a plurality of partitionable engines
US10038550B2 (en) 2013-08-08 2018-07-31 Intel Corporation Instruction and logic to provide a secure cipher hash round functionality
US10140138B2 (en) 2013-03-15 2018-11-27 Intel Corporation Methods, systems and apparatus for supporting wide and efficient front-end operation with guest-architecture emulation
US10146548B2 (en) 2013-03-15 2018-12-04 Intel Corporation Method for populating a source view data structure by using register template snapshots
US10169045B2 (en) 2013-03-15 2019-01-01 Intel Corporation Method for dependency broadcasting through a source organized source view data structure
US10191746B2 (en) 2011-11-22 2019-01-29 Intel Corporation Accelerated code optimizer for a multiengine microprocessor
US10198266B2 (en) 2013-03-15 2019-02-05 Intel Corporation Method for populating register view data structure by using register template snapshots
US10228949B2 (en) 2010-09-17 2019-03-12 Intel Corporation Single cycle multi-branch prediction including shadow cache for early far branch prediction
US4215402A (en) * 1978-10-23 1980-07-29 International Business Machines Corporation Hash index table hash generator apparatus
US4290105A (en) * 1979-04-02 1981-09-15 American Newspaper Publishers Association Method and apparatus for testing membership in a set through hash coding with allowable errors
US4611272A (en) * 1983-02-03 1986-09-09 International Business Machines Corporation Key-accessed file organization
US4730249A (en) * 1986-01-16 1988-03-08 International Business Machines Corporation Method to operate on large segments of data in a virtual memory data processing system
US4736287A (en) * 1983-06-20 1988-04-05 Rational Set association memory system
US4807122A (en) * 1985-04-23 1989-02-21 Mitsubishi Denki Kabushiki Kaisha Information storage system
US4897785A (en) * 1984-09-12 1990-01-30 Bbc Brown, Boveri & Company, Limited Search system for locating values in a table using address compare circuit
US4916658A (en) * 1987-12-18 1990-04-10 International Business Machines Corporation Dynamic buffer control
Horowitz et al., Fund. of Data Structuers in Pascal 1987, pp. 452 467. *
Horowitz et al., Fund. of Data Structuers in Pascal 1987, pp. 452-467.
I.E.E.E. Software 5 (1988) Jul., No. 4, New York, N.Y. USA "Multikey, Exensible Hashing for Relational Databases", pp. 77-85.
I.E.E.E. Software 5 (1988) Jul., No. 4, New York, N.Y. USA Multikey, Exensible Hashing for Relational Databases , pp. 77 85. *
Ralston et al., "Encyclopedia of Computer Science", 1976 p. 267.
Ralston et al., Encyclopedia of Computer Science , 1976 p. 267. *
US6401174B1 (en) 1997-09-05 2002-06-04 Sun Microsystems, Inc. Multiprocessing computer system employing a cluster communication error reporting mechanism
US6449700B2 (en) 1997-09-05 2002-09-10 Sun Microsystems, Inc. Multiprocessing computer system employing a cluster protection mechanism
US6351795B1 (en) 1997-09-05 2002-02-26 Sun Microsystems, Inc. Selective address translation in coherent memory replication
US6324636B1 (en) * 1999-10-15 2001-11-27 Neo Core Inc Memory management system and method
US7171439B2 (en) 2002-06-14 2007-01-30 Integrated Device Technology, Inc. Use of hashed content addressable memory (CAM) to accelerate content-aware searches
US7136960B2 (en) 2002-06-14 2006-11-14 Integrated Device Technology, Inc. Hardware hashing of an input of a content addressable memory (CAM) to emulate a wider CAM
US7373514B2 (en) 2003-07-23 2008-05-13 Intel Corporation High-performance hashing system
US20050044134A1 (en) * 2003-07-23 2005-02-24 Krueger Jon H. High-performance hashing system
US7647462B2 (en) 2003-09-25 2010-01-12 International Business Machines Corporation Method, system, and program for data synchronization between a primary storage device and a secondary storage device by determining whether a first identifier and a second identifier match, where a unique identifier is associated with each portion of data
US20070130216A1 (en) * 2003-09-25 2007-06-07 International Business Machines Corporation Method, system, and program for data synchronization
US7143117B2 (en) 2003-09-25 2006-11-28 International Business Machines Corporation Method, system, and program for data synchronization by determining whether a first identifier for a portion of data at a first source and a second identifier for a portion of corresponding data at a second source match
US20090055833A1 (en) * 2003-11-28 2009-02-26 Allen Hall System and method for performance monitoring
US7890934B2 (en) 2003-11-28 2011-02-15 International Business Machines Corporation System and method for performance monitoring
US7483426B2 (en) * 2004-05-13 2009-01-27 Micrel, Inc. Look-up table expansion method
US7290084B2 (en) 2004-11-02 2007-10-30 Integrated Device Technology, Inc. Fast collision detection for a hashed content addressable memory (CAM) using a random access memory
US7370048B2 (en) * 2005-05-27 2008-05-06 International Business Machines Corporation File storage method and apparatus
US10289605B2 (en) 2006-04-12 2019-05-14 Intel Corporation Apparatus and method for processing an instruction matrix specifying parallel and dependent operations
US8180744B2 (en) * 2008-03-05 2012-05-15 Hewlett-Packard Development Company, L.P. Managing storage of data in a data structure
US9558241B2 (en) * 2009-04-22 2017-01-31 Webroot Inc. System and method for performing longest common prefix strings searches
US20160055213A1 (en) * 2009-04-22 2016-02-25 Webroot Inc. System and method for performing longest common prefix strings searches
US9003247B2 (en) * 2011-04-28 2015-04-07 Hewlett-Packard Development Company, L.P. Remapping data with pointer
US10009172B2 (en) 2012-12-28 2018-06-26 Intel Corporation Instructions processors, methods, and systems to process secure hash algorithms
US10148428B2 (en) 2012-12-29 2018-12-04 Intel Corporation Instruction and logic to provide SIMD secure hashing round slice functionality
US10255076B2 (en) 2013-03-15 2019-04-09 Intel Corporation Method for performing dual dispatch of blocks and half blocks
US10146576B2 (en) 2013-03-15 2018-12-04 Intel Corporation Method for executing multithreaded instructions grouped into blocks
US10248570B2 (en) 2013-03-15 2019-04-02 Intel Corporation Methods, systems and apparatus for predicting the way of a set associative cache
Rader 1981 Memory management in a Viterbi decoder
Cormack et al. 1987 Data compression using dynamic Markov modelling
Kurtz 1999 Reducing the space requirement of suffix trees
EP0970419B1 (en) 2007-07-04 A lempel-ziv data compression technique utilizing a dictionary pre-filled with frequent letter combinations, words and/or phrases
US5525982A (en) 1996-06-11 Method and means for character string pattern matching for compression and the like using minimal cycles per character
US5140321A (en) 1992-08-18 Data compression/decompression method and apparatus
AU626317B2 (en) 1992-07-30 Method and apparatus for encoding, decoding and transmitting data in compressed form
Ferragina et al. 2000 Opportunistic data structures with applications
US7095343B2 (en) 2006-08-22 code compression algorithms and architectures for embedded systems
US7103608B1 (en) 2006-09-05 Method and mechanism for storing and accessing data
US6560610B1 (en) 2003-05-06 Data structure using a tree bitmap and method for rapid classification of data in a database
US5339076A (en) 1994-08-16 Data compression using content addressable memory
Williams et al. 1999 Compressing integers for fast file access
US5325091A (en) 1994-06-28 Text-compression technique using frequency-ordered array of word-number mappers
Raman 1996 Priority queues: Small, monotone and trans-dichotomous
US5781772A (en) 1998-07-14 Compressed prefix matching database searching
US5049881A (en) 1991-09-17 Apparatus and method for very high data rate-compression incorporating lossless data compression and expansion utilizing a hashing technique
US5253325A (en) 1993-10-12 Data compression with dynamically compiled dictionary
US6959300B1 (en) 2005-10-25 Data compression method and apparatus
EP0458698B1 (en) 2000-08-09 Method and apparatus for pointer compression in structured databases
US5924111A (en) 1999-07-13 Method and system for interleaving data in multiple memory bank partitions
EP0650124B1 (en) 2001-07-04 Virtual memory computer system address translation mechanism that supports multiple page sizes
US8200686B2 (en) 2012-06-12 Lookup engine
US5577248A (en) 1996-11-19 Method and apparatus for finding longest and closest matching string in history buffer prior to current string
KR950004247B1 (en) 1995-04-27 Content addressible memory


text:
Home / Current Affairs / Tony Blair declaring war on Islam
Tony Blair declaring war on Islam
Posted by: ʿAbd Allāh Nūr al-Dīn in Current Affairs, Europe, Middle East, Politics, UK 21/11/2014 2 Comments
Despite the fact that Tony Blair has lost credibility amongst the masses, his Tony Blair Faith Foundation has operations in 30 Middle Eastern and African countries where it exports his thinking and has recently discussed domestic policies which strike a disturbing semblance with existing strategies in place. As such I felt it necessary to write a series of pieces on Tony Blair, the neoconservative "persuasion" embedded in his rhetoric, and his proclamations which are reflected in his recent essay which seeks to implement more broadly the contemporary neocon Western foreign policy.
Click here to read Part 1: The "Original Neocon"
Click here to read Part 2: The Neocon Threat to the World
Part 3: "Spectrums" – Declaring War on Islām
It is evident that for Tony Blair, though other factors exist for violence, they are trivial compared to the threat of "Islamism". Be it extremism of other faiths now, or Christian barbarity of the past, "we are dealing with the present" we are told. And in the present, we have the Boko Haram and ISIS. Blair writes that they are fanatic, and "thus it is hard to envisage compromise with such people. They have no reasonable demands upon which we can negotiate." Therefore there is no alternative except to fight such people:
At a certain point, once they know superior and determined force is being used against them, some of them at least may be prepared to change.
In other words, take a leaf out of Israel's book and bomb the people, civilians included, into compliance. Ironically, a month after Blair writing his neocon manual for World War III, ISIS have begun negotiations and are releasing prisoners whilst the Boko Haram have negotiated a truce and have agreed to release the imprisoned girls.[1]
The feed for these groups are the "spectrum" and herein lies Blair's blatant imperialistic design. He defines "Islamism" as a "politicisation of religion to an intense and all-encompassing degree"; an ideology and a theology derived from Salafist thinking. It is not. An analysis of contemporary Islamic political movements (most of which are reactions formed in the colonialist/Nation State paradigm) is beyond the scope of this piece however. Suffice to say, an outright rejection of an Islamic political and military ascendancy denies 1400 years of Islamic history in which Islām ruled through the Caliphate. The existence and the preference for a khilāfa within the Islamic paradigm is a position adopted by all four mainstream schools of Islamic jurisprudence.
The spectrum is elaborated as those people who have an "exclusive, reactionary world view" which is promulgated through the various Islamic seats of learning. Blair elaborates,
a belief in religious exclusivity not merely in spiritual but in temporal terms; a desire to re-shape society according to a set of social and political norms, based on religious belief about Islām, wholly at odds with the way the rest of the world has developed, for example in relation to attitudes to women; a view of the West, particularly the USA, that is innately hostile and regards it essentially as the enemy, not only in policy but in culture and way of living.
Thus, the problem is the notion of returning to status quo ante; a social, political and economic system established on mainstream Islamic principles, at odds with the imposed exploitable development of the "rest of the world" (an arrogant and inaccurate reference to secular liberalism, capitalism and Nation states). The above coupled with his reference to Shaykh Mohamed al-Arefe also highlights his problem with traditional Islamic positions. The upshot is that his "spectrum" is doublespeak for mainstream Islām itself.
Having understood the "spectrum" of Islamism to be Islām, what should happen to the faith? Being at pains to state that it is not a war on peaceful Islām, he declares
"you cannot uproot this extremism unless you go to where it originates and fight it."
The traditional Islamic faith which designates roles for men and women, guides meticulously each and every aspect of life, presents a paradigmatically unique world view which frees man from the subservience of the self to the subservience of God, which recognises Jihād as a means to remove injustice and tyranny, which mandates charity to uplift society and which encourages the establishment of a khilāfa, is to be "fought"; the same Islām which, as Blair recognised in the beginning of his essay, "shamed" the Western world. He McCarthyistically continues,
"World-wide, we should be on the look-out for where there is evidence that Islamist organisations are on the march. Those that fund and support them should know that we're watching, should know that what they want hidden, will instead be exposed to the light."
Liberals are to be supported and the "Islamists" challenged. The enemy is shown to be an extremity (in the guise of various brutalities). The war however, is declared against Islām and its adherents.
Focusing on education Blair writes,
"Each and every day the world over, millions, even tens of millions of young children are taught formally in school or in informal settings, a view of the world that is hostile to those of different beliefs. That world view has been promulgated, proselytised and preached as a result of vast networks of funding and organisation, some coming out of the Middle East, others now locally fostered. These are the incubators of the radicalism. In particular the export of the doctrines of Salafi Wahhabism has had a huge impact on the teaching of Islām round the world."
The irony in the above assessment is that word for word it applies to the secular liberal understanding and the neocon foreign policy. The Trojan Hoax affair is an example of, in essence, forcing an understanding of secularism upon children. This secular liberalism is "exported" around the globe through the discourse of "regime change", human rights and democracy which is, as evident in Blair's own essay, hostile to mainstream Islām. Of course that is not to say all liberals have this mind-set. But the neocons in Western offices in Europe and the US are doing everything to achieve this (I will address the neoconservative policy of exporting liberalism in my Concluding Remarks). This policy is at the very core of British government.
His Foundation has "educational programmes" in various countries. The question is, what sort of education do neocons promote? They claim "mutual respect", but what type of respect? An interesting book authored by neocon Carnes Lord and inspired by Machiavelli's The Prince explores the future of leadership and "statecraft" (a popular term in neoconservative discourse which seeks to create a state in the form of a Platonic dualist society, where the "vulgar many" are ruled by the elite "statesmen" few, with the elite being the only ones capable of guiding society). Approving of a requirement of American and "British history" in curricula, or in the present discourse, "British values" which is linked to a form of "patriotism" (the meaning of which we will soon see), he criticises the decentralisation of education and the lack of direct political involvement in education. Lord looks at universities in England, namely the Oxbridge universities, and Japan's Tokyo University and recognises that they are "virtually integral components of the regime by the fact that they create or validate a national elite", but it is "hard to hold them accountable". In referring to the role of governments establishing schools of "professional education", the real goal desired by neocons from education institutions is brought forth to monitor and manage schools from the beginning "to serve the interests of the state as a whole".[2] The impact of such education is conformity with state policies decided by an elite, turning patriotism into government compliance.
In understanding this, we come to realise that the neocon "education programmes" will achieve the same: a creation of pseudo-elitists versed in the "American way", who serve, through the smokescreen of patriotism, the interests of a state subservient or amenable to Western "interests" and foreign economic and military policies.
Notorious neocon think-tanks like RAND have been targeting youth in the Middle East for their research for years. In the UK, in a Select Committee meeting on "roots of violent extremism",[3] in highlighting a slight tactical change from neoconservatism, Maajid Nawaz says that a "demand for democratic culture" should be created at the grass roots in Muslim countries whilst organisations like Quilliam "tweaks the policy" of the government to supply that demand. In other words, they both instigate and subvert Muslim countries making them more tractable to Western intervention.
Blair calls for a charter to teach "religious respect". This however, already exists in various international legal instruments such as the UN Human Rights Security Council Resolution 16/18 which calls on member states to "speak out against intolerance and religious hatred",[4] an aspect the UK government actively violates with its continuous blusters on "Islamism", fuelling anti-Muslim sentiment and resulting in attacks on Muslim women by a right-wing thugs.[5]
Once again, through the rubric of "religious respect" and "human rights", we have an ideological attack on the faith of Islām. Blair's assertions are to be taken in the context of his essay which seek to reform Islām or crush it if the first aim is unachievable. What is more disturbing is that with Blair's distorted mentality which targets mainstream Islām, his Foundation is operating its brainwashing programs in 30 countries.
"Peace increases our peril"[6]
There was a time when the "Islamists" were admired by the British. Be it the "brave" Afghan Taliban who fought against Communism, or the Ottomans through their tolerant "calm, absorbed Islamism" who staved off Russian Christian extremism. They were admired because there was an interest to be served.
Pealing through Tony Blair's staple neocon doublespeak and uncovering Blair's definition of Islamism, it emerges that the war against Islām is ever-fervent, disguised under the words of human rights, democracy and convoluted epithets.
The reality is that this is the current Western policy and has been for some time. Today the voices and calls for a reformation in Islām are increasing and in parallel, everything is being done to undermine Islamic religious expression through increased securitisation, where an increase in religiosity has become an indicator for "extremism" and an expression against policy or holding the government to account is construed as a stepping stone for terrorism. The latest assault focused on Islām in the education sphere. The categorisation of speakers who propound mainstream Islamic positions as extremism is further evidence. Inherent within these actualities is the castigation of dissent against the Zionist entity and British/Western foreign policy.
Leading neocon and architect of the Iraq war of 2003, the then US defence secretary Paul Wolfowitz stated on the eve of the Iraq war,
"We need an Islamic reformation and I think there is a real hope for one".[7]
The neocons of that time who were busying themselves in creating the mess we have today, attacked the foundations of Islamic learning then, as Tony Blair is doing now. In a speech at Georgetown University on the 30th of October 2003, Wolfowitz described madrassahs as "schools that teach hatred, schools that teach terrorism" while providing free "theologically extremist teaching to 'millions'" of Muslim children.[8] Other neocons went further. Norman Podhoretz – an extreme neocon writer who advocated the Iraq war – in an article calling for war on Iran, explicitly called the war on terror "World War IV" with the enemy being "Islamofascism".[9]
Thus then, as now, during a major war in a Muslim land, to protect "interests" we have the same rhetoric becoming louder from the neocons. Blair has simply refined the old formula to increase upon Western hegemony with minimal resistance where, as per the neocon "mode of thinking", emotion and prejudice is given weight over rationality. Thus, his arguments to whitewash other factors for radicalisation do not hold academically or in reality and is reminiscent of David Cameron's similar, recent attempt to downplay "grievances" in order to pin blame of radicalisation upon "Islamist" ideology.
The irony is, perhaps more so for the Catholic Blair, that Irving Kristol the godfather of neoconservatism, decrying the modernisation attempts of the Catholic Church, advised Catholic leaders to counsel its youngest members to "wear sackcloth and ashes and to walk on nails to Rome".[10]
Islām however, is an open ticket for reformation for the neocons simply because it sits paradoxically with exploitative "interests" of the West which enforces "Hard Wilsonianism" – the foreign policy which pursues "benevolent hegemony" through "intervention", to champion "American ideals" and fight long-term threats to American "interests". This "interest", according to an essay by neocons William Kristol (son of Irving Kristol) and Robert Kagan, "should be the cause of war even when we cannot prove that a narrowly construed 'vital interest' of the United States is at stake".[11] American historian, Professor Greg Grandin elaborating on this policy writes,
"Hard Wilsonianism – that odd mix of unapologetic violence and blinding idealism that motivates neocons – finds it expression in frontline repression, in Abu Graib's and Gitmo's interrogation rooms, in the levelling of Fallujah, and in the scores of unexplained deaths of prisoners in United States custody. It is manifested in the actions of members of the Eighty-second Airborne Division, who for seventeen months, even after the abuses at Abu Ghraib were exposed, beat their Iraqi prisoners with metal baseball bats, perhaps believing that broken bones would make Muslims more receptive to Western values."[12]
Blair then, through his essay has dog-whistled his fellow neocons to sharpen the neocon strategy of perpetual warfare by deception, domestic and abroad. It is a dangerous attack on the faith of over a billion Muslims with a threat of physical coercion.
It is for the Muslim minorities to take stock of the strengthening strategies of old, deceptively garbed in the oratory of human rights in order to fight more than just "hate", but the very foundations of the Islamic faith.
And it is for the upright British citizens to recognise the threat neoconservatism is fostering in Britain. It is hurting Britain. The neocons genuinely believe that perpetual war and fear of an external threat will allow them to mould the state in their vision. As the Straussian neocon Carnes Lord, writes,
Like strategy in war, statecraft is an art of coping with an adversarial environment […] Like strategy, too, statecraft is also an art of relating means to ends. If […]strategy is the art of using wars to achieve the objectives of the war, statecraft is the art of using wars and other instruments available to political leaders to attain national goals.[13]
Their vision has thus far materialised in the continued assault on individual liberty achieved through alarmist statements about security threats. Neoconservatism is destroying the values it claims to believe in and yet it is using them as a vehicle to maintain power for a small elite through demagoguery to shape society as they see fit. It remains to be seen whether Britain continues its trajectory towards a tyrannous future shaped by neocons, or the people of Britain stand up and fight the retroviral "persuasion" known as neoconservatism.
[1] http://www.independent.co.uk/news/world/politics/isis-hostage-threat-which-countries-pay-ransoms-to-release-their-citizens-9710129.html
[2] Carnes, L. The Modern Prince: What Leaders Need to Know Now, R.R. Donnelley & Sons, Virginia US, 2003, pp.139-140.
[3] Home Affairs Committee – Nineteenth Report Roots of violent radicalisation (published 2012), Examination of Witnesses (Questions 45-93), – http://www.publications.parliament.uk/pa/cm201012/cmselect/cmhaff/1446/11091303.htm
[4] Combating intolerance, negative stereotyping and stigmatization of, and discrimination, incitement to violence and violence against, persons based on religion or belief, UN Doc A/HRC/RES/16/18, 12 April 2011, Adopted without voted 24 April 2012
[5] See this report for instances which claims "Muslim hate crime rises 65% in London". – http://www.bbc.co.uk/news/uk-england-london-29424165
[6] Neocon Michael Ledeen in his book, Machiavelli on Modern Leadership, New York: St Martin's Press, 1999 p.70
[7] Riaz, A, Faithful Education: Madrassahs in South Asia, Rutgers University Press, 2004, Cht. 6 Fn.1 p.252
[8] Ibid. p.21
[9] Norman Podhoretz, "The Case for Bombing Iran, I hope and Pray Bush Will Do it", May 30, 2007, http://web.archive.org/web/20090625195336/http://www.opinionjournal.com/federation/feature/?id=110010139
[10] Kristol, I, Neoconservatism: The Autobiagrpahy of an Idea, New York: The Free Press, 1995, p.441
[11] Robert Kagan and William Kristol, Present Dangers: Crisis and Opportunity in American Foreign and Defense Policy, Encounter Books: California, 2000, p.13
[12] Grandin G., Empire's Workshop: Latin America, the United States, and the Rise of the New Imperialism, New York: Holt Paperbacks, 2010, p.234
[13] Carnes, L. The Modern Prince: What Leaders Need to Know Now, R.R. Donnelley & Sons, Virginia US, 2003,* p.24
COUNTER-TERRORISM EDUCATION IRAQ ISIS ISLAMOPHOBIA ISRAEL NEOCON NEOCONSERVATISM PALESTINE SYRIA TERRORISM TONY BLAIR WAR WAR ON TERROR ZIONISM ZIONIST 2014-11-21
ʿAbd Allāh Nūr al-Dīn
Tagged with: COUNTER-TERRORISM EDUCATION IRAQ ISIS ISLAMOPHOBIA ISRAEL NEOCON NEOCONSERVATISM PALESTINE SYRIA TERRORISM TONY BLAIR WAR WAR ON TERROR ZIONISM ZIONIST
Previous: Islamophobia: European history repeating itself?
Next: More Ofsted discrimination against Muslim pupils
About ʿAbd Allāh Nūr al-Dīn
A concerned Muslim with an interest in international law, domestic and foreign policy, history and contemporary ideologies and thinking such as neoconservatism and secularism and their impact on society and in particular Islam and Muslims.
The fact that this proven liar is still given a platform and that his words are taken seriously speaks volumes about the world today.
This is a Shaitian in the guise of a man! Simple! I understand the ignorant masses must be brought up to speed but any Muslim with a basic understanding of the Quran will know that this Shaitan is being used by Iblis to sow the seeds of discord for a long time! We need to call him out by his real title: Shaitan Blair .. Allah tells Adam to name all things and by that we know it implies their properties and natures… we need to become smart again and revisit our texts for the truth… The devils must be outed by us all!
Well done Alhumdulilah great article!
Unscripted #7 | Turning down the Prime Minister!
In this episode, Umer and Salman talk about the Tory leadership race, the Myriad Foundation turning down Theresa May's invite for an "Eid Party", and a unique event raising awareness about autism in mosques.

redpajama_set_name: RedPajamaCommonCrawl


Ok... When it started ...got a call from relative stating several days ago they had a power outage. Went to use garage door discovered spring was broken.. disengaged trolley. They ran the trolley back using opener. It did not stop even when tripping the micro switch on rail. Motor then sparked, also seen something running from the motor... I know details are odd, but this is what I have.
Sounds like the opener may have had a power surge (possibly from a lightning strike) and damaged the opener. The limit switch may have gotten fried along with damage to the logic board...you'll have to physically look at the board...if you see burn marks - it's fried.
The stuff you see running out of the opener is most likely from the capacitor and will need replaced. Depending on how old the opener is it may be better to replace the whole opener instead of trying to replace all the damaged parts.
You know I was leaning to the same conclusion.... BUT was uncertain... going to take a look tomorrow, Thanks for your reply .


Irish insurer FBD is in turmoil after announcing that it has launched an internal inquiry into the activities of its chief executive.
The company, which provides cover in personal lines, commercial lines and farm insurance, announced that the inquiry had been launched following "internal allegations" against CEO Fiona Muldoon.
No details of the allegations are forthcoming.
Muldoon, who is widely credited with turning FBD's fortunes around after major losses, remains in her position while the inquiry continues.
FBD is listed on both the Irish and London stock markets. Canadian investment group Fairfax provided a €70m bailout for the group three years ago, which is convertible into a 20% stake in FBD come September.


2008 release. Guitar-Boy Superstar is the first survey of the long career of the legendary Nigerian musician, artist and poet Victor Uwaifo, one of Nigeria's greatest stars -- a long-overdue release that puts Victor Uwaifo next to other Nigerian greats better known in the West. Victor Uwaifo's mission to spread and preserve the cultural heritage of ancient Benin (Modern day Edo State, Nigeria) has seen him work as a commissioner for cultural affairs in his native Edo State, a University lecturer, acclaimed bronze sculptor and poet as well as a highly successful musician. He has been awarded Nigeria's highest cultural tribute -- the order of the Niger, and continues to teach and work today with an energy that has not abated for nearly fifty years. Cutting his musical teeth with Victor Olaiya ("the evil genius of highlife") in the early '60s, he went on to form his own band The Melody Maestros, producing Nigeria's biggest-ever selling record with Joromi in 1965, for which he was awarded Africa's first gold disc. He has continued to produce some of the most popular and engaging music in Nigeria ever since. This album focuses on his early 1970s musical output. Uwaifo invented a unique style of highlife music that he called ekassa -- based on ancient rhythms and fused with modern highlife instrumentation and just a dash of rock and soul.


I was searching for a Property and found this listing (MLS® #2058863). Please send me more information regarding 6310 E Charleston Boulevard, 203 - East, NV, 89110. Thank you!
I'd like to request a showing of 6310 E Charleston Boulevard, 203 - East, NV, 89110 (MLS® #2058863). Thank you!


self esteem worksheets and activities for teens adults free honesty kindergarten.
kindergarten valentines day activities worksheet printable cute honesty worksheets presidents coloring pages best math for page i a part of under workshee.
free learning worksheets for kindergarteners preschool honesty kindergarten kids under 7 counting.
free character analysis worksheet for kids the measured mom honesty worksheets kindergarten sample.
character education worksheets talking with trees books honesty kindergarten empathy worksheet featuring what if characters.
kindergarten honesty character education lesson plan talking with worksheets free teaches social skills.
collection of honesty worksheets for kids download them and try to kindergarten worksheet.
grade volume worksheets math kindergarten core honesty step 2 worksheet activities printable 4 ki.
honesty worksheets behavior think sheet for preschoolers teaching kindergarten good character.
honesty worksheets for kids in recovery worksheet elegant kindergarten best images on f.
honesty worksheet worksheets kindergarten character education lesson plan talking.
coloring worksheets for kindergarten color bros preschool honesty activity.
responsibility worksheets talking with trees books honesty kindergarten free printable coloring page for teaching respect and self control.


text:
MNN.com > Home > Organic Farming & Gardening
There's a new apple in town
After 20 years in development, the Cosmic Crisp just hit stores.
Mary Jo DiLonardo
It took 20 years of research to create the Cosmic Crisp apple. (Photo: PVM [CC BY-SA 4.0]/Wikimedia Commons)
When you head to the grocery store, look for a new shiny red apple in the produce department. This fruit is being rolled out with incredible fanfare and some pretty big promises.
According to official marketing materials, the Cosmic Crisp is "the apple of big dreams" and "the apple the world has been waiting for." It promises perfect flavor, crisp texture, a juicy interior, striking color and it should be naturally slow to brown.
School lunchboxes have been looking for you forever, Cosmic Crisp.
The Cosmic Crisp apple is the result of two decades of breeding and research at the Washington State University (WSU) Tree Fruit Research and Extension Center. A cross between Enterprise and Honeycrisp apples, Cosmic Crisps taste both sweet and tart, according to the official website. The apples promise to be both good for eating fresh and ideal for cooking and baking.
Because the apples are grown with higher levels of sugar and acidity, they are slow to brown when cut. Cosmic Crisps supposedly will maintain their texture and flavor in storage for more than a year.
Apples started shipping from warehouses in Washington on Dec. 1 and were quickly available in Seattle-area stores. Curious people checked in on Instagram and Facebook to see when the apples would be available in their area. According to the official site, it will take some time for the apple to be available in all parts of the country.
A tempting apple
Known as WA 38 while in development, the apple was tested in focus groups where it earned its catchier name.
The apple has particularly visible pores on its dark skin. And these spots reminded someone in a focus group of twinkling stars in the night sky. That observation inspired the apple's trademarked name.
"It's the first apple that's ever been named by consumers," Kathryn Grandy, the marketing director for Proprietary Variety Management, the company overseeing the apple's national launch, told The California Sunday Magazine. The apple even has its own commercials, like the one above.
The apple tested so well with consumers, reports the magazine, that WSU worked with commercial nurseries to produce saplings as quickly as they could. Originally, they planned to begin with 300,000 trees, but demand from growers grew to 4 million. The first trees were made available to eager growers via lottery.
WSU owns the patent, but the breeding program has been financially supported by the apple industry. WA 38 trees will be exclusive to Washington state growers in the U.S. for at least 10 years, with the clock starting in 2017 when the first commercial orchards were planted.
With this impressive interest and an equally notable $10.5 million marketing budget, it's no wonder Cosmic Crisp is turning heads. But will the taste live up to the hype?
Knute Berger got a bite when he was writing about the apple for Crosscut. He describes it convincingly:
"The Cosmic Crisp ticked every box: good looking, with a nice crunch and powerful snap, a beautiful sweet-tart balance, tons of juice trickling down the chin. I wasn't overwhelmed by, say, hints of blueberry or a floral nose — the kinds of complexities wine tasters go on about. But it was one of the best apples I've ever eaten. In fact, my sample was the essence of apple."
Gala and Red Delicious, don't get too comfortable.
Editor's note: This story has been updated with new information since it was published in August 2019.
Mary Jo DiLonardo writes about everything from health to parenting — and anything that helps explain why her dog does what he does.
Related on MNN:
This amazing way to eat an apple makes the core disappear
10 servings of produce a day? Let's be realistic
9 reasons to eat an apple every day
Related topics: Agriculture, Healthy Eating
After 20 years in development, the Cosmic Crisp apple just hit stores.
6 natural ways to combat anxiety
How helpful is hand sanitizer?


Andre Grant insists he has the perfect plan to beat his next opponent in the UK's premier boxing league, as he prepares to jump back into action to make the first defence of his title next month.
Grant, 25 from Farnborough will put his novice Light Welterweight belt and undefeated record on the line on Saturday May 9th when he travels to the famous Epsom Downs Racecourse in Surrey to meet London rival Thomas King on the undercard of the league's big Unfinished Business promotion, and the champion is supremely confident he'll have more than enough to return home with his perfect record and championship status intact.
Grant claimed the title back in February when he produced the performance of his short career to beat fellow contender Ben Vezza for vacant title in only his second start in the competition, and the champion who represents the Henri's boxing gym in Aldershot believes he is only just getting started as he predicts bigger things to come this year starting on the 9th.
Talking ahead of his next assignment the young champion said: " Winning the belt at the start of the season was incredible, and I'm feeling very confident coming into this first defence against Thomas King.
" Since the last fight I've been hardly out of the gym, and I've also been doing some training over in New York at the world famous Gleeson's boxing gym which was an amazing experience, so I can't wait to lace the gloves back on now and step through those ropes to defend my title.
Grant's first defence will take place on the undercard of the Unfinished Business promotion headlined by the British Middleweight title showdown between champion Gareth Gardner and challenger Lloyd Miller, and to view the rest of the stacked line up click HERE.