smryan@garth.UUCP (sous-realiste) (07/03/90)
>experience was the reverse -- when we replaced an extremely complicated >graph structure with nice vectors and matrices, that section of code became >much MORE reliable. In the case of CDC's EBBO, vector instructions were use to implement an associative memory with a linear orderring. The instructions of the basic block were broken down 24-bit parcels, each of the format 8/0 - zero exponent field. 8/type - type of parcel. 16/info - information of parcel. Each instruction was then separated into a number of parcels. From what I remember, ELEN n,r would become cd.elen opcode parcel. im.n immediate operand n. fo.r implicit fullword operand register r. fr.r fullword destination register r. The scheduler and other subpasses could add more information by adding more parcels, rather than redefining some unified record definition. The parcels were orderred so that execution would proceed from the start of the vector to the end. The advantage of this data structure is that searches could be done based on the 24-bit integers (as 32-bit half reals) streaming through the vector unit at full memory speed, rather than chasing linked list and thrashing the virtual memory. Instructions could be added, deleted, or editted by used vector merge and compress, again at full memory speed, rather relinking the structures and destroying the locality. Someone (Knuth?) described a Fortran compiler that had no symbol table. The source was divided into many multiple key records. By sorting on different groups of keys, relevant informations was brought together for a linear pass. ps. There apparently has been some work on vectorising tabular parsers. -- Her somber eyes consider all ||/+\==/+\|| Steven Ryan that loom and tower, large and tall.||\=/++\=/|| ...!uunet!ingr!apd!smryan Her everyday is always new ||/=\++/=\||...!{apple|pyramid}!garth!smryan and fills her eyes of frail blue. ||\+/==\+/|| 2400 Geng Road, Palo Alto, CA