Method and apparatus for a pipelined DNA memory hierarchy
11515012 · 2022-11-29
Inventors
Cpc classification
G16B50/00
PHYSICS
G11C13/02
PHYSICS
International classification
G06F12/06
PHYSICS
G11C13/02
PHYSICS
Abstract
one embodiment of a memory stores information, including address bits, on DNA strands and provides access using a pipeline of tubes, where each tube selectively transfers half of the strands to the next tube based on probing of associated address bits. Transfers are controlled by logic relating to the state of the tubes: The pipeline may be initialized to start at a high-order target address, providing random access without enzymes, synthesizing probe molecules or PCR at access time. Thereafter, a processing unit gets fast access to sequentially addressed strands each cycle, for applications like executing machine language instructions or reading blocks of data from a file. Another embodiment with a compare unit allows low-order random access. Provided that addresses are encoded using single-stranded regions of DNA where probe molecules may hybridize, other information may use any DNA encoding. Electronic/electrochemical (electrowetting, nanopore, etc.) embodiments as well as biochemical embodiments are possible.
Claims
1. A method for accessing oligonucleotide strands from a memory hierarchy, consisting of a memory tube and a plurality of pipeline tubes, wherein each of said strands encodes information including aw address bits, whereby each of said address bits is able to be probed via biochemical hybridization, the index i is an integer whose value varies between one less than said aw and zero, and ith of said pipeline tubes is referred to as t.sub.i tube, and wherein said memory hierarchy outputs into a t.sub.−1 tube a sequence of subsets of said strands in sequential order determined by said address bits, said method including the steps of: initializing including transferring said strands from said memory tube to a t.sub.aw−1 tube; repeating for each pipeline cycle, the steps of: performing for each said value of said index i, the steps of: obtaining status signals, including s.sub.i status; generating an f.sub.i command; separating a portion of said strands from said t.sub.i tube based on the ith of said address bits into a t.sub.i−1 tube while leaving remaining strands in said t.sub.i tube when said s.sub.i status is asserted; and transferring said remaining strands from said t.sub.i tube into said t.sub.i−1 tube when said s.sub.i status is unasserted and said f.sub.i command is asserted; and processing said strands in said t.sub.−1 tube.
2. The method of claim 1 whereby each said t.sub.i tube in said plurality of said pipeline tubes is composed of an s.sub.i subtube and a c.sub.i subtube, and wherein said step of transferring further includes transferring said remaining strands from said c.sub.i subtube to a s.sub.i−1 subtube when said f.sub.i command is asserted and said s.sub.i status is unasserted, and wherein said step of separating further includes separating said portion of said strands from said s.sub.i subtube based on the ith of said address bits into said s.sub.i−1 subtube while transferring said remaining strands from said s.sub.i subtube into said c.sub.i subtube when said s.sub.i status is asserted, and wherein said step of obtaining said status signals further includes the steps of: asserting said s.sub.i status if said s.sub.i subtube is not empty; and asserting a c.sub.i status if said c.sub.i subtube is not empty.
3. The method of claim 2 wherein said step of generating said f.sub.i command includes the steps of: asserting z.sub.i status when said s.sub.i status is unasserted and said c.sub.i status is unasserted; and evaluating a logic equation from Table 3 that corresponds to said value of said index i as a function of said s.sub.i status, said c.sub.i status, and said z.sub.i status, yielding said f.sub.i command.
4. The method of claim 1 wherein said step of obtaining said status signals further includes the steps of: measuring the approximate number of strands in said t.sub.i tube; asserting said s.sub.i status if said approximate number is large relative to a predetermined midpoint capacity of said t.sub.i tube; and asserting a c.sub.i status if said approximate number is nonzero and less than or equal to said midpoint capacity of said t.sub.i tube.
5. The method of claim 4 wherein said step of generating said f.sub.i command includes the steps of: asserting z.sub.i status when said S.sub.i status is unasserted and said c.sub.i status is unasserted; and evaluating a logic equation from Table 3 that corresponds to said value of said index i as a function of said s.sub.i status, said c.sub.i status, and said z.sub.i status, yielding said f.sub.i command.
6. The method of claim 1 wherein said step of processing further includes the step of returning said strands from said t.sub.−1 tube to said memory tube, and wherein said step of initializing further includes the steps of: obtaining a high-order target; flushing said tubes to return all said strands to said memory tube; transferring said strands from said memory tube to said t.sub.aw−1 tube; and repeating for each bit of said high-order target, the steps of: separating said portion of said strands from said t.sub.i tube based on said ith of said address bits into a t.sub.i−1 tube while leaving said remaining strands in said t.sub.i tube when zero equals the value of said bit of said high-order target; and separating said portion of said strands from said t tube based on said ith of said address bits into said memory tube while transferring said remaining strands into said t.sub.i−1 tube when one equals said value of said bit of said high-order target.
7. The method of claim 6 wherein said step of initializing is performed by an electronic computer that requests access to said sequence of subsets of said strands starting at said high order target, and wherein said step of processing further includes repeating for a number of iterations of said pipeline cycle determined by said electronic computer the steps of: electrochemically sampling a portion of said strands in said t.sub.−1 tube, thereby recovering from said strands in said t.sub.−1 tube said information as electronic information, including electronic address bits corresponding to said address bits; storing at least some of said electronic information into an electronic memory; and manipulating said electronic information from said electronic memory by said electronic computer.
8. The method of claim 7 wherein said step of initialization further includes the step of assigning said high order target to an x count, wherein said step of obtaining said status signals includes the step of copying a f.sub.i+1 command from previous said pipeline cycle, yielding said s.sub.i status, and wherein said step of generating said f.sub.i command includes the steps of: calculating two raised to said value of said index i, yielding a power of two; calculating the sum of said value of said index i plus the value of said x count modulo said value of said power of two, yielding a modulo count; asserting said f.sub.i command if the value of said modulo count equals zero; and incrementing said x count.
9. A method for accessing oligonucleotide strands from a memory hierarchy, consisting of a memory tube and a plurality of pipeline tubes, wherein each of said strands encodes information including aw address bits, whereby each of said address bits is able to be probed via biochemical hybridization, the index i is an integer whose value varies between one less than said aw and zero, and the ith of said pipeline tubes is referred to as t.sub.i tube, and wherein said memory hierarchy outputs into a tube a sequence of subsets of said strands in sequential order determined by said address bits starting at a high order target, said method including the steps of: initializing including the steps of: obtaining said high-order target; flushing said tubes to return all said strands to said memory tube; transferring said strands from said memory tube to said t.sub.aw−1 tube; and unasserting a force command on conclusion of said step of initializing; and repeating for each pipeline cycle, the steps of: performing for each value of said index i, the steps of: obtaining status signals, including an s.sub.i status; generating an f.sub.i command; first separating a portion of said strands from said t.sub.i tube based on the ith of said address bits into a t.sub.i−1 tube while leaving remaining strands in said t.sub.i tube when said s.sub.i status is asserted and said force command is unasserted; second separating said portion of said strands from said t.sub.i tube based on said ith of said address bits into said memory tube while transferring said remaining strands into said t.sub.i−1 tube when said s.sub.i status is asserted and said force command is asserted; and transferring said remaining strands from said t.sub.i tube into said t.sub.i−1 tube when said s.sub.i status is unasserted and said f.sub.i command is asserted; and processing said strands in said tube, said step of initializing further including the step of repeating for each bit of said high-order target, concurrently to repetition of said pipeline cycle, the steps of: unasserting said force command when zero equals the value of said bit of said high-order target; and asserting said force command when one equals said value of said bit of said high-order target.
10. The method of claim 9 wherein said step of initializing is performed by an electronic computer that requests access to said sequence of subsets of said strands starting at said high order target, and wherein said step of processing further includes repeating for a number of iterations of said pipeline cycle determined by said electronic computer the steps of: electrochemically sampling a portion of said strands in said t.sub.−1 tube, thereby recovering from said strands in said t.sub.−1 tube said information as electronic information, including electronic address bits corresponding to said address bits; storing at least some of said electronic information into an electronic memory; and manipulating said electronic information from said electronic memory by said electronic computer.
11. The method of claim 10 wherein said step of initializing further includes giving said s.sub.i status, and a c.sub.i status initial values, wherein said step of generating said f.sub.i command includes evaluating a logic equations from Table 3 that corresponds to said value of said index i as a function of said s.sub.i status, said c.sub.i status, and a z.sub.i status, yielding said f.sub.i command, and wherein said step of obtaining said status signals includes the steps of: keeping said c.sub.i status asserted when said c.sub.i status was asserted in the previous pipeline cycle and said f.sub.i command was unasserted in said previous pipeline cycle; asserting said c.sub.i status when said s.sub.i status was asserted in said previous pipeline cycle and said force command was unasserted in said previous pipeline cycle; asserting said s.sub.i status when f.sub.i+1 command from said previous pipeline cycle was asserted; asserting said s.sub.i status when s.sub.i+1 status from said previous pipeline cycle was asserted; and asserting said z.sub.i status when said s.sub.i status is unasserted and said c.sub.i status is unasserted.
12. The method of claim 9 wherein said step of initializing further includes the steps of resetting a state variable, and of obtaining a low-order target consisting of ceil(log.sub.2(aw)) bits, and wherein said step of processing further includes the steps of: comparing said low-order target against the low-order portion of said address bits of said strands in said t.sub.−1 tube; setting said state variable when said low-order target matches said low-order portion; returning said strands from said t.sub.−1 tube to said memory tube until said state variable is set; and processing only those of said strands in said t.sub.−1 tube which are not returned to said memory tube.
13. The method of claim 12 wherein said step of processing further includes decoding the non-address bits of said strands in said t.sub.−1 tube as a machine language instruction; and executing said machine language instruction by carrying out biochemical reactions in one or more user tubes.
14. The method of claim 13 wherein said step of decoding further includes distinguishing between a branch instruction and a non-branch instruction, and wherein said step of executing said machine language instruction further includes triggering said initialization step using portions of said branch instruction as said high-order target and said low-order target.
15. The method of claim 14 whereby each said t.sub.i tube in said plurality of said pipeline tubes is composed of an s.sub.i subtube and a c.sub.i subtube, and wherein said step of transferring further includes transferring said remaining strands from said c.sub.i subtube to a s.sub.i−1 subtube when said f.sub.i command is asserted and said s.sub.i status is unasserted, and wherein said step of separating further includes separating said portion of said strands from said s.sub.i subtube based on the ith of said address bits into said s.sub.i−1 subtube while transferring said remaining strands from said s.sub.i subtube into said c.sub.i subtube when said s.sub.i status is asserted, and wherein said step of obtaining said status signals further includes the steps of: asserting said s.sub.i status if said s.sub.i subtube is not empty; and asserting a c.sub.i status if said c.sub.i subtube is not empty.
16. The method of claim 15 wherein said step of generating said f.sub.i command includes the steps of: asserting z.sub.i status when said s.sub.i status is unasserted and said c.sub.i status is unasserted; and evaluating a logic equation from Table 3 that corresponds to said value of said index i as a function of said s.sub.i status, said c.sub.i status, and said z.sub.i status, yielding said f.sub.i command.
17. The method of claim 16, whereby said user tubes include a.sub.0 tube and a.sub.1 tube, wherein said step of decoding further includes distinguishing COMBINE0, COMBINE1, SEPARATE1 and SET1 instructions, and wherein said step of executing said machine language instruction further includes: combining strands from said a.sub.0 tube into a tube specified by said machine language instruction and combining strands from said a.sub.1 tube into said a.sub.0 tube when said machine language instruction is said COMBINE1; combining strands from said tube specified by said machine language instruction into said a.sub.0 tube when said machine language instruction is said COMBINE0; separating said strands from said a.sub.0 tube based on a bit position specified by said machine language instruction into said a.sub.1 tube when said machine language instruction is said SEPARATE1 while leaving remaining strands in said a.sub.0 tube; and setting a bit position specified by said machine language instruction in said strands from said a.sub.0 tube via biochemical hybridization when said machine language instruction is said SET1.
18. A memory hierarchy accessing oligonucleotide strands, wherein each of said strands encodes information including aw address bits, whereby the value of each of said address bits is able to be probed via biochemical hybridization, wherein the number of said strands is nr, the integer parameter r is greater or equal to one, and the integer parameter n is no more than two raised to the power of said aw, including: a memory tube capable of holding all said strands; a pipeline of aw tubes, wherein the first of said aw tubes, known as T.sub.1, can hold at least nr of said strands, is connected to said memory tube and is operative for probing the first of said aw address bits, wherein the second of said aw tubes, known as T.sub.2, can hold at least nr/2 of said strands, is connected to said T.sub.1 and is operative for probing the second of said aw address bits, and wherein the third of said aw tubes, known as T.sub.3, can hold at least nr/4 of said strands, is connected to said T.sub.2 and is operative for probing the third of said aw address bits, wherein said pipeline continues similarly to the last of said aw tubes, known as T.sub.aw, wherein said T.sub.aw can hold at least 2r of said strands, is connected to T.sub.aw−1, and is operative for probing the last of said aw address bits; a processing unit for holding at least r of said strands, wherein said processing unit is connected to said T.sub.aw; and logic for receiving external control inputs and for receiving a plurality of status from said aw tubes, and in response for generating a plurality of commands to said aw tubes, whereby said commands cause said tubes to probe said strands and to selectively transfer subsets of said strands through said pipeline, thereby providing said processing unit with a sequence of said subsets of said strands having sequential patterns of said address bits as guided by said external control inputs.
19. The memory hierarchy of claim 18 wherein one of said aw tubes, known as T.sub.i, operative for probing the ith of said aw address bits further comprises: an input pipe capable of transferring n′ of said strands, wherein the integer parameter n′ is said integer parameter r times two raised to the power aw−i+1; an output pipe capable of transferring n′/2 of said strands; a chamber capable of holding n′ of said strands; a S.sub.i status output to said logic, wherein said S.sub.i status is asserted when said chamber contains more than approximately 3n′/4 of said strands; and a C.sub.i status output to said logic, wherein said C.sub.i status is asserted when said chamber is not empty but contains less than approximately 3n′/4 of said strands, wherein said chamber operative for separating a portion of said n′ strands via said output pipe based on said ith of said address bits while leaving remaining strands in said chamber when said S.sub.i status is asserted, operative for transferring said remaining strands from said chamber via said output pipe and for transferring said n′ strands via said input pipe to said chamber when said S.sub.i status is unasserted and said logic asserts an F.sub.i command, operative for combining said n′ strands transferred via said input pipe with said remaining strands in said chamber when said S.sub.i command is unasserted and said F.sub.i status is unasserted.
20. The memory hierarchy of claim 19 wherein said logic generates said F.sub.i command according to the logic equations in Table 3, whereby said F.sub.i is synonymous with f.sub.aw−i, said S.sub.i is synonymous with s.sub.aw−i, and said C.sub.i is synonymous with c.sub.aw−i.
21. The memory hierarchy of claim 18 wherein one of said aw tubes, known as T.sub.i, operative for probing the ith of said aw address bits further comprises: an input pipe capable of transferring n′ of said strands, wherein the integer parameter n′ is said integer parameter r times two raised to the power aw−i+1 an output pipe capable of transferring n′/2 of said strands a first chamber capable of holding n′ strands, an S.sub.i status output to said logic, wherein said S.sub.i status is asserted when said first chamber is not empty a second chamber capable of holding n′/2 of said strands, a C.sub.i status output to said logic, wherein said C.sub.i status is asserted when said second chamber is not empty, wherein said first chamber is operative for separating a portion of said n′ strands via said output pipe based on said ith of said address bits while transferring remaining strands to said second chamber when said S.sub.i status is asserted, and for transferring said n′ strands via said input pipe to said first chamber when said S.sub.i status is unasserted, and wherein said second chamber is operative for receiving said remaining strands from said first chamber when said S.sub.i status is asserted, and for transferring said remaining strands from said second chamber via said output pipe when said S.sub.i status is unasserted and said F.sub.i command is asserted.
22. The memory hierarchy of claim 21 wherein said logic generates said F.sub.i command according to the logic equations in Table 3, whereby said F.sub.i is synonymous with f.sub.aw−i, said S.sub.i is synonymous with s.sub.aw−i, and said C.sub.i is synonymous with c.sub.aw−i.
23. The memory hierarchy of claim 18 wherein one of said aw tubes, known as T.sub.i, operative for probing the ith of said aw address bits further comprises: an input pipe capable of transferring n′ of said strands, wherein the integer parameter n′ is said integer parameter r times two raised to the power aw−i+1; an output pipe capable of transferring n′/2 of said strands; a return pipe capable of returning said strands to said memory tube; an external flush command for indicating when all said strands should return to said memory tube via said return pipe; an external force command for indicating the initial high-order address bits to be received by said processing unit; a chamber capable of holding n′ of said strands; a S.sub.i status output to said logic, wherein said S.sub.i status is asserted when said chamber contains more than approximately 3n′/4 of said strands; and a C.sub.i status output to said logic, wherein said C.sub.i status is asserted when said chamber is not empty but contains less than approximately 3n′/4 of said strands, wherein said chamber is operative for returning said strands from said chamber to said memory tube via said return tube when said flush command is asserted, operative for separating a portion of said n′ strands via said output pipe based on said ith of said address bits while leaving remaining strands in said chamber when said S.sub.i status is asserted, said force command is unasserted and said flush command is unasserted, operative for separating a portion of said n′ strands to said memory tube via said return pipe based on said ith of said address bits while transferring remaining strands via said output pipe when said S.sub.i status is asserted, said force command is asserted and said flush command is unasserted, operative for transferring said strands from said chamber via said output pipe and for transferring said n′ strands via said input pipe to said chamber when said S.sub.i status is unasserted and said flush command is unasserted and said logic asserts an F.sub.i command, operative for combining said n′ strands transferred via said input pipe with said strands in said chamber when said S.sub.i status is unasserted and said F.sub.i command is unasserted and said flush command is unasserted.
24. The memory hierarchy of claim 23 wherein said logic generates said F.sub.i command according to the logic equations in Table 3, whereby said F.sub.i is synonymous with f.sub.aw−i, said S.sub.i is synonymous with s.sub.aw−i, and said C.sub.i is synonymous with c.sub.aw−i.
25. The memory hierarchy of claim 24 wherein said processing unit is further operative for returning said subsets of said strands to said memory tube via said return pipe.
26. The memory hierarchy of claim 25 further including comparison unit connected between said T.sub.aw and said processing unit, operative for returning said subsets of said strands to said memory tube via said return pipe from the time an external initialization command is asserted until the time said subset of said strands have low-order address bits that match external bits, and operative for passing through said subsets of said strands from said T.sub.aw to said processing unit at all other times.
Description
DRAWING—FIGURES
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
DETAILED DESCRIPTION
(10) Referring to
(11) Referring to
(12) Referring to
(13) Suppose a tube (T.sub.0) that contains naked strand 9100 (representing ‘000’) and strand complex 9300 (representing ‘101’) has a series of identical molecules like probe 9403. One will hybridize with the naked strand 9100 because the associated bit position is a ‘0’. Another will remain unhybridized, leaving strand complex 9300 free to move about in the solution that contains the strands.
(14) If an external magnetic field 9900 is applied, and the solution is forced out of the tube, the complex 9300 will be carried away (presumably to another tube, T.sub.1, not shown), leaving the naked strand 9100 attached to the magnetic probe 9303. The magnetic probe 9303 may be melted away and magnetically removed, leaving the strand with a bit ‘0’ separated from a strand with a bit of ‘1’. The sticker system conceptualizes this as an algorithmic step, SEPARATE(T.sub.1, T.sub.0, T.sub.0, bitpos).
(15) Referring to
(16) Simultaneously, the processing unit 100 may return a previous memory strand to the pipelined DNA memory hierarchy 1000 via pipe 300 because under normal circumstances neither the processing unit 100 nor the pipelined DNA memory hierarchy 1000 creates or destroys DNA strands. A typical application of pipelined DNA memory hierarchy 1000 is where processing unit 100 treats the data portion of DNA memory strands as conventional machine language instructions to be executed. Those skilled in the art will understand the datapath of such an execution unit would also be pipelined, and processing unit 100 might take several pipeline stages before it returns a particular DNA memory strand via pipe 300. An entirely different application of pipelined DNA memory hierarchy 1000 would be the assembly of larger DNA nanostructures from individual mostly single-stranded DNA delivered to processing unit 100 from pipelined DNA memory hierarchy 1000 in the order they need to be attached to the nanostructure (Arnold, et al. 2017). In such applications, the processing unit 100 consumes the DNA strands, and they would not be returned via pipe 300. One can imagine other applications where circular mostly double-stranded plasmid-like DNA strands (only the address portion is uncovered) are used by processing unit 100 for protein synthesis before being returned via pipe 300. Yet another application is as a DNA Disk drive attached to a conventional electronic computer.
(17) Regardless of the application envisioned for processing unit 100, during normal operation, one memory strand will appear each clock cycle in the sequential order defined by the address portion of the DNA strands. For example, with five-bit binary address DNA memory strands (consistent with the example aw=5 of
(18) The pipelined DNA memory hierarchy 1000 includes a controller 5000 interconnected with logic 4000. The signals sent from controller 5000 to logic 4000 include the force signal 5001, the initialize signal 5002, the freeze signal 5003 and the flush signal 5004; these signals 5001, 5002, 5003 and 5004 deal with abnormal or atypical conditions. The controller 5000 and logic 4000 may be implemented electronically using digital logic and/or microprocessors. Alternatively, the controller 5000 and logic 4000 may be implemented biochemically. The controller 5000 and logic 4000 sequence the remaining components of the DNA memory hierarchy 1000, which may be implemented electrochemically (e.g., electrowetting as in PurpleDrop) or biochemically (machinery built from other kinds of DNA, RNA, protein, etc. molecules that act to contain and process the distinct Adleman-like or Roweiss-like DNA strands that records the address and data being discussed from this point on).
(19) These electrochemical-or-biochemical components include an optional comparison unit 2000 (which assists in initial random accessing of an arbitrary binary starting address so that the first DNA strand output via pipe 200 matches the desired low-order starting address, i.e., earlier addresses are filtered out) and a series of DNA tubes 1010, 1110, 1210, 1310, 1410, . . . , 3000. The comparison unit is unnecessary if low-order ceil(log.sub.2(aw)) bits of the starting address are zero, and in certain special cases, but is necessary for arbitrary (stride one) random access. DNA tube 3000 at times may hold all the DNA memory strands prior to initial random access. This memory tube 3000 is sometimes called M. The other tubes 1010, 1110, 1210, 1310, 1410, . . . may hold various subsets of the DNA memory strands in a pipelined process that arranges them into sequential order for eventual output from comparison unit 2000 via pipe 200. In little-endian-zero-origin notation tube 1010 is called to, where the lower-case-bold indicates the choice of this notation, which is used in source code descriptions later. Those skilled in the art will realize an identical apparatus can be described in other ways, such as big-endian-one-origin notation, where tube 1010 is called T.sub.aw, which in this example would be T.sub.5. Tubes 1110, 1210, 1310, 1410 may be referred to as t.sub.1, t.sub.2, t.sub.3 and t.sub.4 or as T.sub.4, T.sub.3, T.sub.2 and T.sub.1. Using big-endian-one-origin notation may be considered easier to describe these tubes in English, but those skilled in the art will realize, although the descriptions in the two notations are different because the subscripts are transformed, they describe identical ideas.
(20) Successively smaller subsets of DNA strands are transferred via pipes 1560, . . . , 1460, 1360, 1260, 1160 and 1060. Pipe 1060 transfers at most one strand (there may be redundant copies of this one strand) per cycle to be filtered (if necessary) by comparison unit 2000 before being output on pipe 200. The signals sent from controller 5000 to comparison unit 2000 include the desired-starting-address low-order bits 5010, 5011, 5012, . . . , the force signal 5001, the initialize signal 5002, the freeze signal 5003 and the flush signal 5004. The initialize signal 5002 changes the internal state of comparison unit 2000 so that it discards (via pipe 2309) strands input via pipe 1060 until it finds a strands whose low-order address bits match desired-starting-address low-order bits 5010, 5011, 5012, . . . Finding such a strand alters the state of the comparison unit 2000 so that for normal operation from that moment onward it passes through (to pipe 200) all strands input via pipe 1060. This is the reason why controller 5000 occasionally needs to assert the initialize signal 5002 when it wants to alter the normal operation of the pipeline. The initialize signal 5002 also causes memory tube 3000 to transfer its contents via pipe 1560 to the adjacent tube, which in the five-bit example of
(21) The logic 4000 generates 3-bit tube controls 1030, 1130, 1230, 1330, 1430, . . . corresponding to the respective DNA tubes 1010, 1110, 1210, 1310, 1410, . . . Each of the 3-bit controls 1030, 1130, 1230, 1330, 1430, . . . allows for eight distinct behaviors of the corresponding tubes 1010, 1110, 1210, 1310, 1410, . . . during a clock cycle. Those skilled in the art will realize other arrangements besides 3-bit controls are possible. During normal operation, (when strands appear in pipe 200 in sequential order), each control signal will indicate that the corresponding tube should perform either a) combining strands currently residing in the tube with strands transferred from the tube's right input (no strands are transferred out of the tube during such a cycle); b) transferring strands currently in the tube towards the unit on the left while simultaneously and independently transferring strands from the tube's right input to become the new tube contents (the biochemical equivalent of a flip flop); or c) separating and transferring strands currently in the tube that record a ‘0’ in a particular bit position to the unit on the left while simultaneously and independently combining strands that record a ‘1’ in that bit position with any strands transferred from the tube's right input. Those skilled in the art of digital design will realize that the role of ‘0’ and ‘1’ may be interchanged. The bit-position within the strand that is tested is a design parameter that is distinct in each of the tubes 1010, 1110, 1210, 1310, 1410, . . . At times other than normal operation (such as initial random access, flushing or freezing the pipeline) a tube needs additional commands, such as sending strands to be recycled into the memory tube 3000, which will be discussed in more detail later.
(22) Each of the DNA tubes 1010, 1110, 1210, 1310, 1410, . . . is designed to recognize whether it holds approximately more or less than a particular number of strands. This number is some constant (including r, the number of strands that are redundant with identical information on each strand, or that at least have identical address bits if distinct information is recorded in the non-address portion of the strand) times two raised to the bit-position parameter described in the separate operation. This predetermined midpoint (n′) parameter of DNA tube 1110 is twice this parameter of DNA tube 1010, and so forth proceeding from left to right in
(23) Each of the DNA tubes 1010, 1110, 1210, 1310, 1410, . . . generates an s.sub.i status signal 1040, 1140, 1240, 1340, 1440, . . . when the particular DNA tube holds more strands than its corresponding design parameter; each of the DNA tubes 1010, 1110, 1210, 1310, 1410, . . . generates an c.sub.i status signal 1050, 1150, 1250, 1350, 1450, . . . when the particular DNA tube is not empty but holds fewer strands than its corresponding design parameter. The s.sub.i and c.sub.i are not bold because they are not tubes. They are simple signals that may be implemented biochemically, electrically, or electrochemically. Their subscripts correspond to the subscripts of the tubes and should be consistent. Here, lower case indicates little-endian-zero-origin. Analogous big-endian-one-origin description for these signals would be C.sub.i and S.sub.i.
(24) Referring to
(25) After initialization is complete, at time x=1, things get more involved. Simultaneously, tube 1010 transfers the remaining stand (1) via pipe 1060c as output, while tube 1110 transfers its contents (2,3) to tube 1010 via pipe 1160c. Between x=1 and x=2, pipes 1060c and 1160c are shown as solid lines and have the “c” suffix because these are total transfers (in sticker terminology, “COMBINE” operations). The net effect at time x=2 makes tube 1010 full with new contents (2,3), but leaves tube 1110 empty, a situation shown as “10 00 01 01”. Between x=2 and x=3, pipe 1260c transfers the entire contents of tube 1210 to tube 1110 and pipe 1060s separates out the next output (2), leaving 3 in tube 1010. Also, simultaneously, tube 1210 transfers (via solid line 1260c) its remaining contents (4 . . . 7) into tube 1110. At x=3, this new situation is shown as “01 10 00 01”. Between x=3 and x=4, pipe 1060c outputs 3. Also, tube 1110 separates half its strands (4,5) via pipe 1160s to tube 1010, leaving the other half (6,7) in tube 1110. At x=4, this is shown as “10 01 00 01”. Between x=4 and x=5, there are no transfers between tubes. Since 4 has been output from tube 1010, it is half full with the other tubes unchanged, and this appears as “01 01 00 01”. Between x=5 and x=6, the entire contents (6,7) of tube 1110 is transferred to tube 1010 via pipe 1160c, and the entire contents (8 . . . f) of tube 1310 is transferred to tube 1210 via pipe 1360c, which is shown as “10 00 10 00”.
(26) If it is difficult to implement a tube that distinguishes such numbers of strands, an equivalent tube may be implemented by using two subtubes: an s.sub.i subtube that holds the full number and its non-empty condition indicates more than the particular number of strands and a c.sub.i subtube that holds half that number as a result of the separating operation that emptied the s.sub.i subtube; testing the emptiness of these two subtubes gives the information needed in the previous paragraphs. Like tubes, subtubes are shown in bold. Again, the lower case indicates little-endian-zero-origin. Analogous big-endian-one-origin description is possible with upper-case-bold C.sub.i and S.sub.i. Referring to
(27) If both the subtube approach and the approach of measuring the approximate number of strands against the midpoint parameter prove too costly to implement, the s.sub.i and c.sub.i status may be generated by digital electronic logic. Referring to
(28) There are two ways to indicate the state of the pipeline. The most natural way from the user's perspective is to describe the address x which will issue from the pipeline at the end of a given clock cycle. In the previous cycle, it would have been x−1 (i.e. during the current cycle, x−1 has just been removed from the pipeline). In the following cycle, it will be x+1 (i.e. during the next cycle, x will have been removed from the pipeline). Values of x≤0 represent initial cycles needed to fill the pipeline. An alternate way to know the state of the pipeline is by the pattern of subtubes that are not empty in a given cycle, which is what has been discussed earlier. The following analyzes the connection between the pattern of tubes that are not empty and the binary state x.
(29) It is possible to analyze the state transitions independently of the tube contents M that are distributed among the subtubes s.sub.i and c.sub.i. Let the non-boldface variable (with the additional subscript x) s.sub.x,i mean that the s.sub.i subtube is not empty corresponding to the binary state x of the pipeline. Similarly, the variable c.sub.x,i mean that the c.sub.i subtube is not empty corresponding to the binary state x and the variable z.sub.x,i mean that both subtubes are empty corresponding to the binary state x. The following recurrence describes in little-endian-zero-origin notation the pipeline state transition corresponding to x>1−aw:
(30)
where f(x,k)=(x+k)≡0 mod 2.sup.k. If the x subscripts are eliminated above, and it is noted that the goal of logic 4000 in pipeline cycle x is to compute f.sub.i=f(x,i), those skilled in the art will also note that the state machine of
(31) From this recurrence, we could display the evolution of the pipeline (left column of Table 1) visually using:
(32) ‘s’ when s.sub.x,i indicates the ith pipeline stage is occupied by the “separate” subtube,
(33) ‘c’ when c.sub.x,i indicates the ith pipeline stage is occupied by the “combine” subtube,
(34) ‘ ’ when z.sub.x,i indicates the ith pipeline stage has zero strands.
(35) The algorithmic action of the pipeline is clearer with a slightly different notation (right column of Table 1):
(36) ‘c’ when c.sub.x,i indicates the ith pipeline stage is occupied by the “combine” subtube while simultaneously f(x,k) indicates a transfer (COMBINE operation) will occur,
(37) ‘|’ when c.sub.x,i indicates the ith pipeline stage is occupied by the “combine” subtube but the transfer does not occur
(38) TABLE-US-00004 TABLE 1 Example Evolution of the Pipeline −3 s s −2 sc sI −1 scc sII 0 sccc sIII 1 cccc ccII 2 s cc s CI 3 cs c cs I 4 sc c sI I 5 cc c cc C 6 s s s S 7 csc csI 8 scc sII 9 ccc ccI 10 s c s C 11 cs cs 12 sc sI * 13 cc s cc S 14 s sc s SI 15 cscc csII
Analogous information is given in the table in
f.sub.k=f(X(s.sub.0, . . . s.sub.aw−1,c.sub.0, . . . ,c.sub.aw−1),1).
Note that the arguments may be truncated after the i−1 column (little-endian notation) because f(x,i) is a modulo-2.sup.i function, and we can overload the semantics of X so that the meaning is clear (the variables with subscripts >i are don't cares). Because of this cyclical pattern, the logic equations for f.sub.i may be obtained most easily by inspection of the tail of the state transitions, i.e., the line shown for 2.sup.aw−i reveals the logic equation for as illustrated in Table 2 for aw=11. In Table 2, ‘.’ is don't care, and ‘z’ is shown instead of ‘ ’, and the left number is i, indicating the f.sub.i revealed by the pattern shown for x=2.sup.aw−i.
(39) TABLE-US-00005 TABLE 2 Transition for the tail of pipeline evolution for aw = 11 i x 10 2038 szszzzzzzz . 9 2039 csczzzzzz . . 8 2040 scczzzzz . . . 7 2041 ccczzzz . . . . 6 2042 szczzz . . . . . 5 2043 cszzz . . . . . . 4 2044 sczz . . . . . . . 3 2045 ccz . . . . . . . . 2 2046 sz . . . . . . . . . 1 2047 c . . . . . . . . . .
(40) Referring to
(41) TABLE-US-00006 TABLE 3 Logic equations f.sub.1 = c.sub.0 f.sub.2 = s.sub.0z.sub.1 f.sub.3 = c.sub.0c.sub.1z.sub.2 f.sub.4 = c.sub.0c.sub.1z.sub.2z.sub.3 f.sub.5 = c.sub.0s.sub.1z.sub.2z.sub.3z.sub.4 f.sub.6 = s.sub.0z.sub.1c.sub.2z.sub.3z.sub.4z.sub.5 f.sub.7 = c.sub.0c.sub.1c.sub.2z.sub.3z.sub.4z.sub.5z.sub.6 f.sub.8 = s.sub.0c.sub.1c.sub.2z.sub.3z.sub.4z.sub.5z.sub.6z.sub.7 f.sub.9 = c.sub.0s.sub.1c.sub.2z.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8 f.sub.10 = s.sub.0z.sub.1s.sub.2z.sub.3z4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9 f.sub.11 = c.sub.0c.sub.1z.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10 f.sub.12 = s.sub.0c.sub.1z.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11 f.sub.13 = c.sub.0s.sub.1z.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12 f.sub.14 = s.sub.0z.sub.1c.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13 f.sub.15 = c.sub.0c.sub.1c.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14 f.sub.16 = s.sub.0c.sub.1c.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15 f.sub.17 = c.sub.0s.sub.1c.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16 f.sub.18 = s.sub.0z.sub.1s.sub.2c.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17 f.sub.19 = c.sub.0c.sub.1z.sub.2s.sub.3z.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18 f.sub.20 = s.sub.0c.sub.1z.sub.2z.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19 f.sub.21 = c.sub.0s.sub.1z.sub.2z.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20 f.sub.22 = s.sub.0z.sub.1c.sub.2z.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21 f.sub.23 = c.sub.0c.sub.1c.sub.2z.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22 f.sub.24 = s.sub.0c.sub.1c.sub.2z.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23 f.sub.25 = c.sub.0s.sub.1c.sub.2z.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23z.sub.24 f.sub.26 = s.sub.0z.sub.1s.sub.2z.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23z.sub.24z.sub.25 f.sub.27 = c.sub.0c.sub.1z.sub.2c.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23z.sub.24z.sub.25z.sub.26 f.sub.28 = s.sub.0c.sub.1z.sub.2c.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23z.sub.24z.sub.25z.sub.26z.sub.27 f.sub.29 = c.sub.0s.sub.1z.sub.2c.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23z.sub.24z.sub.25z.sub.26z.sub.27z.sub.28 f.sub.30 = s.sub.0z.sub.1c.sub.2c.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23z.sub.24z.sub.25z.sub.26z.sub.27z.sub.28z.sub.29 f.sub.31 = c.sub.0c.sub.1c.sub.2c.sub.3c.sub.4z.sub.5z.sub.6z.sub.7z.sub.8z.sub.9z.sub.10z.sub.11z.sub.12z.sub.13z.sub.14z.sub.15z.sub.16z.sub.17z.sub.18z.sub.19z.sub.20z.sub.21z.sub.22z.sub.23z.sub.24z.sub.25z.sub.26z.sub.27z.sub.28z.sub.29z.sub.30
(42) The controller 5000 issues flush signal 5004 to the logic 4000 and to the comparison unit 2000 when it wishes all strands to be returned to memory tube 3000. The controller 5000 needs this to be completed prior to the sequence of steps required for random accessing of an arbitrary binary starting address. When flush signal 5004 is issued, logic 4000 generates 3-bit tube controls 1030, 1130, 1230, 1330, 1430, . . . corresponding to the respective DNA tubes 1010, 1110, 1210, 1310, 1410, . . . that cause DNA tubes 1010, 1110, 1210, 1310, 1410, . . . to empty all the DNA strands they contain via pipes 1020, 1120, 1220, 1320, 1420, . . . Also, when flush signal 5004 is issued, comparison unit 2000 empties all the DNA strands it contains via pipe 2309. The DNA strands in pipes 300, 2309, 1020, 1120, 1220, 1320, 1420, . . . are combined together into pipe 3020 and transferred into memory tube 3000. This may take one or more clock cycles to accomplish depending on implementation details. In addition to when flush signal 5004 is issued, pipe 3020 transfers DNA strands back to memory tube 3000 when the processing unit 100 is done with them; when the comparison unit 2000 have filtered them out (because they don't match the starting-address); or when the controller 5000 issues the force signal 5001. This latter case, when then controller issues the force signal 5001, is part of sequence of steps required for random accessing of an arbitrary binary starting address.
(43) The complete sequence of steps required for random accessing of an arbitrary binary starting address is as follows: 1. The controller 5000 issues flush signal 5004 to the logic 4000 and to the comparison unit 2000 so that all DNA strands will be returned to memory tube 3000. 2. The controller waits (if necessary) the proper number of cycles for this to be completed. 3. The controller 5000 issues initialize signal 5002 to comparison unit 2000, along with desired-starting-address low-order bits 5010, 5011, 5012, . . . , so that comparison unit 2000 is prepared to filter out strands that do not match the desired-starting-address low-order bits 5010, 5011, 5012, . . . The initialize signal 5002 also causes memory tube 3000 to transfer its contents via pipe 1560 to the adjacent tube, which in the five-bit example of
(44) Referring to
(45) Tube 2110 is configured to act as a separating tube based on the next-significant-address bit of its input strands, with outputs pipes 2120 (with strands whose bit is ‘0’) and 2130 (with strands whose bit is ‘1’). Pipe 2120 is input to demuxiplexer 2140 which transfers these strands either to pipe 2160 or to pipe 2170 based on the next-significant-starting-address bit 5011. Pipe 2130 is input to demuxiplexer 2150 which transfers these strands either to pipe 2190 or to pipe 2180 based on the next-significant-starting-address bit 5011. Pipes 2160 and 2190 are combined into pipe 2108. Pipes 2102, 2170 and 2180 are combined into pipe 2109. The net effect is that strands whose next-significant address bit matches the next-significant-starting-address bit 5011 are transferred into comparison tube 2210, while those that don't are transferred into reject tube 2201, whose output is pipe 2102 (which also has those that did not match the earlier stage).
(46) Tube 2210 is configured to act as a separating tube based on the further-significant-address bit of its input strands, with outputs pipes 2220 (with strands whose bit is ‘0’) and 2230 (with strands whose bit is ‘1’). Pipe 2220 is input to demuxiplexer 2240 which transfers these strands either to pipe 2260 or to pipe 2270 based on the further-significant-starting-address bit 5012. Pipe 2230 is input to demuxiplexer 2250 which transfers these strands either to pipe 2290 or to pipe 2280 based on the further-significant-starting address bit 5012. Pipes 2260 and 2290 are combined into pipe 2208. Pipes 2202, 2270 and 2280 are combined into pipe 2209. The net effect is that strands whose further-significant address bit matches the further-significant-starting-address bit 5012 are transferred into reject tube 2310, while those that don't are transferred into reject tube 2301 (which also has those that did not match the earlier stages).
(47) At this stage, tube 2310 contains strands that match the starting-address bits 5010, 5011 and 5012, while tube 2301 contains those that do not. Signal 2319 indicates whether tube 2310 is empty or not. If signal 2319 indicates tube 2310 is empty, state machine 2318 does not change its state (the initialize signal 5002 created this state at the beginning). If signal 2319 indicates tube 2310 is not empty, state machine 2318 changes to the non-initial state. The flag output 2317 of state machine 2318 reflects its current state, and controls demultiplexer 2305. If flag 2317 indicates the state machine 2318 is still in the initialize state, demultiplexer 2305 transfers strands from pipe 2302 onto pipe 2306, where they will be combined into pipe 2309 and recycled back to the memory tube 3000. In other words, if state machine 2318 is still in the initialize state, such strands will not be output by the comparison unit 2000. On the other hand, if flag 2317 indicates the state machine 2318 is no longer in the initialize state, demultiplexer 2305 transfers strands from pipe 2302 onto pipe 2307 which is combined with pipe 2370. This means the one DNA strand that matched the low-order-starting address on pipe 2370 and all DNA strands that follow in later cycles on pipe 2307 will be transferred into tube 2410, whose output pipe 200 connects to processing unit 100.
(48) During the first cycle the flush signal 5004 is asserted, tubes 2101, 2201, 2301, 2310 and 2410 empty their contents via pipes 2103, 2203, 2303, 2330 and 2430, respectively. Pipes 2306, 2103, 2203, 2303, 2330 and 2430 are combined into pipe 2309 and recycled back to the memory tube 3000. Tubes 2010, 2110 and 2210 are using both of their outputs for other purposes, and are not emptied by the flush signal 5004. (Here there are three such tubes; in general there would be log.sub.2(aw) such tubes.) Instead strands in those tubes 2010, 2110 and 2210 travel naturally through the pipeline until they arrive at one of the other tubes 2101, 2201, 2301, 2310 and 2410. This means, as suggested earlier, it takes multiple cycles to flush the pipeline. The specific example of
Applications of the Present Invention
(49) One application of the present invention is to store instructions for processor 100 when it is a biochemical processor that executes machine language. Most conventional electronic processors use a Random Access Memory (RAM) in which the address is not recorded with the contents. Typically, such machines have two distinct registers: a program counter (PC) that provides the address, and an Instruction Register (IR) which holds a copy of the current instruction associated with that PC. Instead, the present invention acts like a Content Addressable Memory (CAM), where contents and address are both recorded on each strand. The role of the PC and IR have been merged into a single PCIR tube, another name for t.sub.−1 (provided by pipe 200 to processor 100), which holds a single strand on which both an instruction and its associated address within the larger program are encoded. Control flow is implemented by choosing one instruction/address strand from many in a Memory (M) tube and moving that strand to the PCIR, after first transferring the old strand from the PCIR back to M, which is the natural operation of the pipeline in the present invention. During normal execution, no new machine-language strands are created, copied or destroyed; they simply cycle in and out of the PCIR following the flow of control of the program.
(50) The following shows instructions for a one-address machine, using two accumulator tubes a.sub.0 and a.sub.1, where an address field specifies a bit address for some instructions (SET1 and SEPARATE1) and a tube address (in the user tubes u.sub.i) for other instructions (variations of combine that transfer into and out of the accumulator tubes). The one-address ISA could be emulated by the following:
(51) COMBINE0(t) {COMBINE(a.sub.0, t);}
(52) SEPARATE1(i) {SEPARATE(a.sub.1, a.sub.0, i);}
(53) SET1(i) {SET(a.sub.0,i);}
(54) COMBINE1(t) {COMBINE(t, a0); COMBINE(a0, a1);}
(55) The COMBINE0 instruction plays the role that an arithmetic instruction plays in a conventional one-address ISA. Two accumulator tubes are needed because SEPARATE1 assumes these rather than allowing the user to specify them in software. The two accumulator tubes act like a tiny stack, with COMBINE1 playing the role of a store/pop instruction that transfers a.sub.1 to a.sub.0 after combining the old a.sub.0 into the t specified by the user tube address. The following suggests the type of operations that processing unit 100 performs after the comparison unit 2000 has delivered the instruction to PCIR:
(56) fetchExecutel( ) {SEPARATE(temp,PCIR, iw−2); SEPARATE(temp,PCIR, iw−1); if (!EMPTY(temp)) CAMinst( ); else execute1( ); COMBINE(M, PCIR); }
The constant iw is the instruction width, including the aw bits that specify the address. If the two most-significant bits (iw−1 and iw−2) are both zero, a non-CAM instruction is executed. If either of these bits are one (meaning the PCIR has moved to temp), CAMinst handles cases like jump instructions (which trigger a pipeline initialization). The one-address non-CAM instruction is handled simply by execute1, based on previously established contents of a.sub.0 and a.sub.1:
(57) execute1( ) {computeOp( ); decoder(3); //eight tubes or bits of data for (i=0; i<8; i=i+1) {if (!EMPTY(d.sub.i)) {if (op==0) INIT(a.sub.0); if (op==1) SET(a.sub.0, i); //SET0 if (op==2) SEPARATE(a.sub.1, a.sub.0, a.sub.0, i); //SEPARATE0 if (op==3) COMBINE(a.sub.0, u.sub.i); //COMBINE0 if (op=4) {COMBINE(u.sub.i, a.sub.0); COMBINE(a.sub.0,a.sub.1);}//COMBINE1 . . . }} unDecoder(3); }
(58) decoder(n) (COMBINE(d.sub.0, PCIR); for (i=0; i<n; i=i+1) {for (j=0; j⇐(1<<i)−1; j=j+1) SEPARATE (d.sub.(1<<i)+j, d.sub.j, d.sub.j, i+aw); }} unDecoder(n) {for (i=0; i<(1<<n); i=i+1) COMBINE(PCIR, d.sub.i); }
First, computeOp copies bits that identify the operation from PCIR into a controller variable op. Calls to decode and unDecode determine the bit or tube address. After decode, one of eight (in this example) d.sub.i tubes contains the instruction; which tube is not empty determines the value of i. Using computeOp simplifies the controller and allows the code to say things like (op==2), but the decoder approach could be used there also. COMBINE1 and COMBINE0 reference user tubes, u.sub.i. Although it takes two “COMBINE” operations to specify op=4, these may execute in parallel (as illustrated by the general tube module of the Verilog code in Appendix 1) allowing the pipeline to proceed without freezing, because every possible non-CAM instruction executes in one cycle. The unDecoder operation combines the d.sub.i tubes, which allows the instruction strand which was in one of them to be returned to M. The CAM instructions, on the other hand, require the pipeline to freeze and/or initialize.
(59) Another application of the present invention is using DNA as a replacement for a disk drive. The information is stored on multiple strands with unique addresses. Just as a disk drive slowly seeks a sector to provide random access, followed by a fast sequential read of contiguous blocks of data, the present DNA memory hierarchy initializes its pipeline (requiring about aw cycles) to access the first set of stands, followed by fast sequential access. Electrochemical sampling a portion of the addressed strands using technology such as a nanopore sensor allows the information encoded on the strand to be converted to electronic information, which can be stored in a conventional electronic memory for further processing. Assuming redundancy and error coding is used, the recovered information in the electronic memory can be corrected for errors. Although the concept of a DNA disk is not new, the present invention makes it more feasible to implement because it allows fast bursts of data transfer after random access. In contrast, the prior art (such as Milenkovic et al., Kashiwamura et al.) provides random access by slow PCR (requiring many cycles) to provide selective amplification of the strands to be accessed. In the prior art, to continue reading sequentially after electrochemically converting the first set of strands requires additional PCR, whereas the present invention can process one addressed set of strands per cycle. Furthermore, unlike addressing by PCR, which contaminates and/or dilutes the supply of memory strands, the present invention does not modify, change or destroy any memory strands.
(60) Referring to
Description of the Appendices
(61) In order to fully describe and simulate the system described by
(62) The natural operation of the pipeline may be described by a recursive function, which is given in C code in Appendix 2. A concise definition of this function is:
(63)
where the boldface m indicates the function returns a sets of strands, the function H(m,k) returns a set of strands of higher values (with bit k set, in other words half of the separate operation), the function L(m,k) returns a set of strands lower values (with bit k cleared in other words the other half of the separate operation), inm gives initial values, and |m| measures the number of strands compared against 3n′4=1.5r2.sup.k−1. The non-tail recursion of this definition makes it inefficient to run, but it is a compact description of how the pipeline works, and it allows mathematical reasoning about its operation. It is closely tied to the definition of s.sub.i and c.sub.i. The C program uses a bit set internal representation. Because of the limitations of C long long, it can only simulate tubes with no more than 64 strands. Like the Verilog code, it makes multiple copies of its internal representation, even though in the biochemical system only one copy exists.
(64) Appendix 3 gives several C programs that print “s”/“c” patterns for the DNA memory hierarchy similar to Table 2, including one (pipeinc6xlogeqn.c) with outputs them in a logic-equation form similar to Table 3. Together these demonstrate the essential logical correctness of the present invention without having to simulate at the strand level. The first program, pipeinc1.c, is an early version (DNA23 poster) using a parametric equation in little-endian-one-origin (to avoid mentioning Li). The next program (pipeinc2x.c) introduces the variable x mentioned earlier. The next (pipeinc3x.c) changes to zero origin notation for consistency with this specification. The next three (pipeinc3xfun . . . pipeinc5xfun.c) use f(x,i). The next two (pipeinc6xfunsc.c and pipeinc6xlogeqn.c) use the recurrence for s.sub.i and c.sub.i, which shows the validity of the ASM chart in
(65) Appendix 4 gives a Java class that simulates the full memory hierarchy (including compare unit 2000, and associated high-order-bit initialization) for all possible random access cases. In other words, there are 2048 random accesses, many of which require (up to 15) extra cycles for the compare unit 2000 to discard the extra strands that come before the start of the desired address. For each of these cases, the rest of memory from that point to 2047 is accessed. In other words, the simulation makes about 2.sup.21 sequential accesses producing significant output, proving that the initialization, compare unit 2000 and logic 4000 work for every possible case. There are two initialization approaches that can be used, depending on which method is called at the line with the “*****” comment: a) like the Verilog code of Appendix 1, using precisely the aw−ceil(log.sub.2(aw)) bits as the high-order address (Java method is fetchpipeplay2), and b) for certain addresses recognized by Java method fetchpipeplay, use additional high-order bits to reduce the extra cycles needed for random access. The Java code also computes the average number of extra cycles (beyond the aw=11 needed for pipeline initialization): a) 7.5625 and b) 2.0957. The hardware of
(66) There are many options to enable arbitrary random access to the pipeline, and the following explains the background behind the options discussed above. A naive implementation would simply iterate the pipeline start times. On average, this would take 2.sup.aw−1 iterations, which is much too slow. Recall x=X(s.sub.0, . . . s.sub.aw−1, c.sub.0, . . . , c.sub.aw−1). Because there is a one-to-one mapping between the pattern of s.sub.x,i and c.sub.x,i variables and a given 0≤x<2.sup.aw, an inverse function exists:
X.sup.−1(x)=(s.sub.x,0, . . . s.sub.x,aw−1,c.sub.x,0, . . . ,c.sub.x,aw−1)
Random access to an address, start, simply means initializing the pipeline state to X.sup.−1(start). One idea would be to force all tubes into the correct state based on the bits of the entire address, which, surprisingly, we will see by itself will not quite work in every case, but which provides a foundation. Below on the left is code for fetchpipe to initialize c.sub.i and s.sub.i subtubes tubes. It uses Sakar-Ghosal probing of individual bits of a strand contained in an addr tube and a temp tube to sense the value of the bit (so the target address is on a strand which would be useful when the memory hierarchy is part of a totally biochemical processor executing a machine language branch instruction on the strand), but the details being explained may be lost in the use of a temp tube. For clarity, similar code, fetchpipestart, on the right uses an integer variable, start, to indicate the same thing, and for which the probing of its bits is done with conventional masking. The fetchpipestart approach is closer to an implementation of a DNA disk drive attached to a conventional electronic computer that would issue start, and receive the equivalent electronic information from the addressed strands. What matters for understanding the pipeline initialization is that the COMBINEs and SEPARATEs are identical in both functions.
(67) fetchpipe(addr,temp) fetchpipestart(start) { combine (s.sub.aw−1,M); {combine (s.sub.aw−1,M); for (i=aw−1; i>0; i=i−1) for (i=aw−1; i>0; i=i−1) {SEPARATE(temp,addr,addr,i+aw); { if (!ISEMPTY(temp)) if (((1<<i)&start) !=0) SEPARATE(s.sub.i−1,M,s.sub.i,i); SEPARATE(s.sub.i−1,M,s.sub.i,i); else else SEPARATE (c.sub.i,s.sub.i−1,s.sub.i, i); SEPARATE (c.sub.i, s.sub.i−1,s.sub.i, i); combine(addr,temp); } } SEPARATE(temp,addr,addr,i+aw); if (!ISEMPTY(temp)) if ((l&start) !=0) SEPARATE (c.sub.0,M,s.sub.0,0); SEPARATE(c.sub.0,M,s.sub.0,0); combine(addr,temp); } }
Address bit 0 is not processed inside the for loop. Instead, there is a later if statement that only does something for odd addresses. Let's consider the case that start is zero. Since every bit is zero, each time through the loop the SEPARATE after the else causes c.sub.i to get H(s.sub.i,i) and s.sub.i−1 to get L(s.sub.i,i). In other words, among the s subtubes, only s.sub.0 is not empty, and among the c subtubes only c.sub.0 is empty. This matches the first four lines of Table 1. Next, let's consider start=1. This is similar, except the if statement dealing with odd addresses causes a further SEPARATE so that all s subtubes are empty and all c subtubes are not empty, which matches the x=1 line of Table 1. Finally, consider when start is a power of two. On the ith iteration, the SEPARATE after the if causes the unneeded lower-valued strands (that proceed start) from the ith subtube (L(s.sub.i,i)) to be returned to M (rather than stay in the pipeline) and the remaining higher-valued strands (H(s.sub.i,i)) to be moved into subtube s.sub.i−1. This leaves both s.sub.i and c.sub.i empty.
(68) In order to know whether fetchpipestart works, we can initialize the pipeline and check whether it outputs all strands sequentially from start to 2.sup.aq−1. A slightly modified version of the Java simulator in Appendix 4 has tested cases up to aw=32 which verify that fetchpipestart sometimes works, for values of start such as 0, 1, 2, 4, 5, 8, etc. It also works for powers of two. Unfortunately, fetchpipestart by itself fails to work for cases like 3, 6, 7, 11, 13, 14, 15, etc. In these situations, the pipeline starts to output the first expected strands, but then freezes. This happens because higher tubes have not been prepared with the proper contents. The upper-case letters and ‘*’ in Table 1 show how the pipeline prepares these tubes during its normal evolution. (The ‘*’ shows where a ‘C’ would have been if aw had been larger.) When we use fetchpipestart, we are jumping over that evolution. For some cases (like powers of two), fetchpipestart just happens to put the pipeline in the same state that the slow evolution from 0 to start would cause. But for cases on a line immediately after one of the upper-case letters or ‘*’ in Table 1, fetchpipestart makes a mistake. These are on lines 2, 5, 6, 10, 12, 13, 14, . . . The failed values of start are always one more than the number of these lines. (These patterns hold not just for the small example in Table 1, but in exhaustive simulations too extensive to reproduce here.) The upper case ‘C’s and ‘S’s, proceeded by one or more spaces, are bringing higher-valued strands into lower-numbered tubes where they will be needed in only a few clock cycles. There is a mathematical pattern that allows us to recognize the set of values 3, 6, 7, 11, 13, 14, 15, . . . which cause this problem. These cases satisfy
2.sup.nN+1−nN≤start mod 2.sup.nN+1,
where 1<nN≤aw−2 is the upper bound on the number of extra operations needed to correct the problem. We can think of the largest value that satisfies this as being a function of start. Computing nN(start) requires bit-wise operations as well as addition and comparison:
(69) getnN(int start) { int i,nN; nN=0; for (i=1; i<=aw−2; i++) //don't do MSB { if ((1<<(i+1))−i ⇐ (((1<<(i+1))−1) &start) ) nN=i; } return nN; }
More abstractly, for an argument 0≤x<2.sup.aw, there are several useful properties of nN(x): First, nN(x)≤aw−2 because it is defined this way. If nN(x)≠0, there exists an iN≤nN(x) such that nN(x−iN). Also, for all integers 0≤i<2.sup.aw−ceil(log 2(aw)), nN(i2.sup.ceil(log 2(aw)))=0. Values of start for which nN(start)=0 are exactly the cases where fetchpipestart works by itself, which is the reason the embodiment of the present invention given in
(70) A cheaper alternative (which would eliminate the need for comparison unit 2000 in the context of a biochemical processor where the pipeline is only being used to fetch instructions, and the initialization problem only arises with branch instructions) would do the calculation of nN during compilation, and insert NOPs into the object code generated by the compiler such that the target of all branch addresses satisfy nN=0. This is possible because each region in which nN>0 is preceded and followed immediately by a region in which nN=0. This compile-time alternative would increase code size, and decrease speed of a compiled program that will depend on the properties of the individual program being compiled. Every target address would be preceded by a variable number of NOPs that would not have been needed for a processor with correct hardware pipeline initialization as provided by
(71) In the context of a DNA disk drive, it may be reasonable to require all random access to use only aw−ceil(log.sub.2(aw)) high-order bits, thereby eliminating the need for comparison unit 2000. This would be analogous to seeking a sector (or a track) on a mechanical drive, and then reading several blocks sequentially, where the stride of access for the present invention would be 2.sup.ceil(log 2(aw)).
(72) The idea of random access by iterating start times is exponentially slow, but trying to arrive directly at the pipeline state for every case of start is difficult when nN(start)≠0.
(73) fetchpipe4(addr,temp) fetchpipe4(addr,temp) { combine (s.sub.aw−1,M); {combine (s.sub.aw−1,M); for (i=aw−1; i>4; i=i−1) for (i=aw−1; i>4; i=i−1) {SEPARATE(temp,addr,addr,i+aw); { SEPARATE(temp,addr,addr,i+aw); if (!ISEMPTY(temp)) force=!ISEMPTY(temp); SEPARATE (s.sub.i−1,M,s.sub.i,i); else pipecycle( ); SEPARATE (c.sub.i,s.sub.i−1,s.sub.i,i); combine(addr,temp); combine(addr,temp); } } force=0; for (i=3; i>=0; i=i−1) for (i=3; i>=0; i=i−1) {SEPARATE(temP,addr,addr,i+aw); { SEPARATE(temP,addr,addr,i+aw); st[i]=!ISEMPTY(temp); st[i]=!ISEMPTY(temp); combine(addr,temp); combine(addr,temp); SEPARATE(s.sub.i−1,M,s.sub.i,i); if (i>0) SEPARATE (c.sub.i,s.sub.i−1,s.sub.i,i); } } } }
The one on the left (fetchpipe4) uses SEPARATEs analogously to fetchpipe (and is very similar to fetchpipeplay2 in Appendix 4); the one on the right uses the force approach shown in
(74) A faster alternative is possible for random access. The masking of the low ceil(log.sub.2(aw)) bits of start can be thought of as computing iN=start mod 2.sup.ceil(log 2(aw)) which will guarantee nN(start−iN). Masking is a simple operation, but it ignores that smaller values of iN might suffice, which could be a compromise between masking and the optimum. Table 4 shows a selective masking scheme which is a better compromise, and that is compatible with the hardware of
(75) TABLE-US-00007 TABLE 4 Selective masking of start avoids masking in most cases when nN(start) = 0. . . . . . . . . . . . . .01x [2, 3] => 2 . . . . . . . . . . . .01xx [4, 7] => 4 . . . . . . . . . . .011xx [12, 15] => 12 . . . . . . . . . .011xxx [24, 31] => 24 . . . . . . . . .0111xxx [56, 63] => 56 . . . . . . . .01111xxx [120, 127] => 120 . . . . . . .011111xxx [248, 255] => 248 . . . . . .0111111xxx [496, 511] => 496 . . . . .0111111xxxx [1008, 1023] => 1008 . . . .01111111xxxx [2032, 2047] => 2032 . . .011111111xxxx [4080, 4095] => 4080 . .0111111111xxxx [8176, 8192] => 8176 .01111111111xxxx [16368, 16384] => 16368 011111111111xxxx [32752, 32768] => 32752
Selective masking occurs when a zero is followed by a group of ones immediately before the masked bits (denoted by ‘x’); the number of masked bits depends on where the group of ones start. The decimal intervals beside each mask describe the first such case where the rule applies; the number after “.Math.” is the decimal value that all values within the interval are mapped into; don't cares (‘.’) encompass many other cases. Note that all cases (3, 6, 7, 11, 13, 14, 15 . . . ) that fail without masking are included within one of the intervals (when don't cares are also considered, as 11 is 1011.sub.2, which is the “0.01 x” case).
CONCLUSIONS, RAMIFICATIONS AND SCOPE
(76) Accordingly, the reader will understand the pipelined DNA memory hierarchy provides random access to a high-order address, using the pipeline initialization techniques disclosed without having to use enzymes, synthesize probe molecules or perform PCR at access time. Also, the reader will understand the pipeline then provides fast access to sequential addresses each cycle thereafter. Such properties make such embodiments desirable for several applications, including, but not limited to, execution of machine language instructions and reading of successive blocks of data from a file.
(77) Although the description above contains many specificities, these should not be construed as limiting the scope of the embodiments but as merely providing illustrations of some of several embodiments. For example, the testing of whether the subtubes s.sub.i and c.sub.i are empty could be implemented either as testing whether there are any strands in the subtube or more simply as whether there is any fluid in the subtube. The latter test might be more easily achieved in a video-controlled electrowetting system like PurpleDrop. Furthermore, although
(78) Thus, the scope of the embodiments should be determined by the appended claims and their legal equivalents, rather than by the examples given.
(79) TABLE-US-00008 Appendix 1: Verilog Simulation of a 5-bit DNA Memory Hierarchy ′define K 10 //number of total bits in strands, must be >=aw ′define aw 5 //number of address bits ′define NUMST (1<<′aw) //number of strands allows all possible addrs tested //modules define wires with size [′NUMST*(′K+1)−1:0] //allow simulation of transport of 0 to ′NUMST strands together in a cycle //The (′K+1)bits of each strand indicates whether that strand exists //If(′K+1)bit==0, that pos available in a combine to hold additional strand //Since NUMST large enough, if combine called properly always be room //In biochemical system, stand with particular address exists only in one place //In simulation, sometimes need temp copies of strands for a moment //Misusing combine with copies can cause COMBINE OVERFLOW (too many strands) //following simulates demux and tube modules // combine is a function (inside def of tube) which can be called with // instanceoftube.combine(a,b) // where a and b are wire['NUMST*(′K+1)−1:0] // can optimize instanceoftube.combine(a,b) to be a|b // when it is known either a or b is empty module demux (o1,o0,i,status); output o1,o0; input i; input status; wire [′NUMST*(′K+1)−1:0] o0; wire [′NUMST*(′K+1)−1:0] o1; wire [′NUMST*(′K+1)−1:0] i; assign o0 =status ? 0 : i; assign o1 =status ? i : 0; endmodule module tube(o1,o0,i,cmd,status,c1k); parameter BIT = 1; parameter LABEL = “ ” parameter CUTOFF = (3<<BIT)>>1; output o1,o0; input i; input [2:0] cmd; //{force,s_i,f_i} output [1:0] status; input clk; reg [′NUMST*(′K+1)−1:0] o1; reg [′NUMST*(′K+1)−1:0] o0; wire [′NUMST*(′K+1)−1:0] i; reg [′NUMST*(′K+1)−1:0] t; assign status = {getTubePop(t)>CUTOFF, (getTubePop(t)<=CUTOFF)&&(getTubePop(t) !=0)); function [′K:0] getStrand; input[′NUMST*('K+1)−1:0] in; input i; integer i; begin getStrand = ((1<<(′K+1))-1) & (in>>( (′K+1)*i)); end endfunction function [′NUMST*(′K+1)−1:0] putStrand; input [′NUMST*(′K+1)−1:0] in; input i; input [′K:0] newstrand; integer i; begin putStrand = (( ~( ((1<<(′K+1))-1)<<((′K+1)*i)) ) &in) | (newstrand<<( (′K+1)*i)); end endfunction function [′NUMST*(′K+1)−1:0] initStrand; input 1; integer 1; reg [′NUMST*(′K+1)−1:0] i1; integer i; begin if ((1>′K)||((1<<1)>′NUMST)) begin $display(“L too big”); $stop; end i1 −\= 0; for (i=0; i< (1<<1); i=i+1) begin i1-putStrand(i1,i,i|(1<<'K)); end initStrand =i1; end endfunction function [′NUMST*(′K+1)−1:0] reverse; input[′NUMST*(′K+1)−1:0] in; reg [′NUMST*('K+1)−1:0] result; integer i,j; begin result = 0; j = ′NUMST−1; for (i=0; i< ′NUMST; i=i+1) begin result=putStrand(result,j,getStrand(in,i)); j =j-1; end reverse = result; end endfunction function [′NUMST*(′K+1)−1:0] compress; input[′NUMST*(′K+1)−1:0] in; reg [′NUMST*(′K+1)−1:0] result; integer i,j; begin result = 0; j = 0; for (i=0; i< ′NUMST; i =i+1) begin if ((getStrand(in,i)>>′K)==1) begin result=putStrand(result,j,getStrand(in,i)); j = j+1; end end compress = result; end endfunction function integer getTubePop; input[′NUMST*(′K+1)−1:0] in; integer i; integer count; begin count = 0; for (i=0; i< ′NUMST; i=i+1) begin if ((getStrand(in,i)>>′K)==1) count = count + 1; end getTubePop = count; end endfunction function [′NUMBT*(′K+1)−1:0] combine; input[′NUMST*(′K+1)−1:0] i; input[′NUMST*(′K+1)−1:0] t; begin if (getTubePop(i)+getTubePop(t)>′NUMST) $display(“COMBINE OVERFLOW”); combine = compress(t)|reverse(compress(i)); end endfunction function [′NUMST*(′K+1)−1:0] H; input[′NUMST*(′K+1)−1:0] in; input kk; integer kk; reg [′NUMST*(′K+1)−1:0] result; integer i; begin result = 0; for (i=0; i< ′NUMST; i =i+1) begin if (((getStrand(in,i)>>′K) ==1)&&((((getStrand(in,i)>>kk)&1) ==1))) begin result=putStrand(result,i,getStrand(in,i)); end end H = result; end endfunction function [′NUMST*(′K+1)−1:0] L; input[′NUMST*(′K+1)−1:0] in; input kk; integer kk; reg [′NUMST*(′K+1)−1:0] result; integer i; begin result = 0; for (i=0; i< ′NUMST; i=i+1) begin if (((getStrand(in,i)>>'K)==1)&&((((getStrand(in,i)>>kk)&1)==0))) begin result=putStrand(result,i,getStrand(in,i)); end end L = result; end endfunction function isEmpty; input[′NUMST*(′K+1)−1:0] in; integer i; reg isEmp; begin isEmp = 1; for (i=0; i< ′NUMST; i =i+1) begin isEmp = ((getStrand(in,i)>>′K)==0) & isEmp; end isEmpty =isEmp; end endfunction task displayStrands; input[′NUMST*(′K+1)−1:0] in; integer i; reg [K:0] mask; begin mask = (1<<′K)-1; for (i=0; i< ′NUMST; i =i+1) begin if ((getStrand(in,i) >>′K) ==1) $write(“%d”,getStrand(in,i)&mask); end $display(″ ″); end endtask task displayStrandsRaw; input[′NUMST*(′K+1)−1:0] in; integer i; begin for (i=0; i < ′NUMST; i =i+1) begin //if ((getStrand(in,i)>>′K ==1) $write(“%b”,getStrand(in,i));//&((1<<′K)−1),“ ”); end $display(“ ”); end endtask always @(posedge clk) begin case(cmd) 3′b000: t <= combine(i,t); 3′b001: t <= i; 3′b010: t <= combine(i,U(t,BIT)); 3′b011: t <= combine(i,H(t,BIT)); 3′b100: t <= combine(i,t); 3′b101: t <= i; 3′b110: t <= i; 3′b111: t <=i ; endcase end always @(t or cmd) begin case(cmd) 3′b000: o0 = 0; 3′b001: o0 = 0; 3′b010: o0 = 0; 3′b011: o0 = 0; 3′b100: o0 = 0; 3′b101: o0 = 0; 3′b110: o0 = L(t,BIT); 3′b111: o0 = t;//L(t,BIT); endcase end always @(t or cmd) begin case(cmd) 3′b000: o1 = 0; 3′b001: o1 = t; 3′b010: o1 = L(t,BIT); 3′b011: o1 = L(t,BIT); 3′b100: o1 = 0; 3′b101: o1 = t; 3′b110: o1 = H(t,BIT); 3′b111: o1 = 0;//H(t,BIT); endcase end always @(posedge clk) if (LABEL != “ ”) begin #1 $write($time,“ %s bit=%d stat=%b t=”,LABEL,BIT,status); //displayStrandsRaw(t); displayStrands(t); $write($time, “ %s cmd=%b i=”,LABEL,cmd); displayStrands(i); $write($time,“ %s cmd=%b o1=”,LABEL,cmd); //displayStrandsRaw(o1); displayStrands(o1); $write($time,“ %s o0=”,LABEL); //displayStrandsRaw(o0); displayStrands(o0); $display(“ ”); end endmodule // comments in modules below give ref nums corresp. to figs module compare(ok4,rrcomb,o0,st,initialize,freeze,flush,clk); //2000 output ok4; //200 output rrcomb; //2309 input o0; //1060 input st; //5010-5012 input initialize; //5002 input freeze; //5003 input flush; //5004 input clk; reg [′NUMST*(′K+1)−1:0] rrcomb; //2309 wire [′NUMST*(′K+1)−1:0] 00; //1060 wire [′NUMST*(′K+1)−1:0] ok4; //200 wire [2:0] st; //5010-5012 wire initialize; //5002 wire freeze; //5003 wire flush; //5004 wire clk; wire [′NUMST*(′K+1)−1:0] rr3; //2303 wire [′NUMST*(′K+1)−1:0] rr2; //2203 wire [′NUMST*(′K+1)−1:0] rr1; //2103 wire [′NUMST*(′K+1)−1:0] ro4; //2430 wire [′NUMST*(′K+1)−1:0] ro3; //2330 wire [′NUMST*(′K+1)−1:0] cp0_1; //2030 wire [′NUMST*(′K+1)−1:0] cp0_0; //2020 wire [′NUMST*(′K+1)−1:0] dm0_0_0; //2060 wire [′NUMST*(′K+1)−1:0] dm0_0_1; //2070 wire [′NUMST*(′K+1)−1:0] dm0_1_0; //2080 wire [′NUMST*(′K+1)−1:0] dm0_1_1; //2090 tube #(0,“ ”) cmp0(cp0_1,cp0_0,o0,{~freeze,~freeze,1′b0},,clk);//2010=cmp0 tube demux dmx0_0(dm0_0_1, dm0_0_0, cp0_0, st[0]); //2040=dmx0_0 demux dmx0_1(dm0_1_1, dm0_1_0, cp0_1, st[0]); //2050=dmx0_1 wire [′NUMST*(′K+1)−1:0] rj0 = dm0__0_1 | dm0_1_0; //2009 = combine(impl w|only 1 inp has strand) wire [′NUMST*(′K+1)−1:0] ok0 = dm0_0_0 | dm0_1_1; //2008 = combine(impl w|only 1 inp has strand) wire [′NUMST*(′K+1)−1:0] cp1_1; //2130 wire [′NUMST*(′K+1)−1:0] cp1_0; //2120 wire [′NUMST*(′K+1)−1:0] dm1_0_0; //2160 wire [′NUMST*(′K+1)−1:0] dm1_0_1; //2170 wire [′NUMST*(′K+1)−1:0] dm1_1_0; //2180 wire [′NUMST*(′K+1)−1:0] dm1_1_1; //2190 wire [′NUMST*(′K+1)−1:0] rj0oui-; //2102 tube #(0,“ ”) rej1(rj0out,rr1,rj0,{flush,flush,(~freeze)|flush},,clk); //2101 = rej1 tube tube #(1,“ ”) cmp1(cp1_1,cp1_0,ok0,{~freeze,~freeze,1′b0},,clk); //2110 = cmp1 tube demux dmx1_0(dm1_0_1, dm1_0_0, cp1_0, st[1]); //2140 =dmx1_0 demux demux dmx1_1(dm1_1_1, dm1_1_0, cp1_1, st[1]); //2150 =dmx1_1 demux wire [′NUMST*(′K+1)−1:0] rj1 =dm1_0_1 | dm1_1_0 | rj0out; //2109 = combine(impl w|only 1 inp has strand) wire [′NUMST*(′K+1)−1:0] ok1 =dm1_0_0 | dm1_1_1; //2108 = combine(impl w|only 1 inp has strand) wire [′NUMST*(′K+1)−1:0] cp2_1; //2230 wire [′NUMST*(′K+1)−1:0] cp2_0; //2220 wire [′NUMST*(′K+1)−1:0] dm2_0_0; //2260 wire [′NUMST*(′K+1)−1:0] dm2_0_1; //2270 wire [′NUMST*(′K+1)−1:0] dm2_1_0; //2280 wire [′NUMST*(′K+1)−1:0] dm2_1_1; //2290 wire [′NUMST*(′K+1)−1:0] rj1out; //2202 tube #(0,“ ”) rej2(rj1out,rr2,rj1,}flush,flush,(~freeze)|flush},,clk); //2201 = rej1 tube tube #(2,“ ”) cmp2(cp2_1,cp2_0,ok1,}~freeze,~freeze,1′b0},,clk); //2210 = cmp2 tube demux dmx2_0(dm2_0_1, dm2_0_0, cp2_0, st[2[); //2240 = dmx2_0 demux demux dmx2_1(dm2_1_1, dm2_1_0, cp2_1, st[2]); //2250 =dmx2_1 demux wire [′NUMST*(′K+1)−1:0] rj2 =dm2_0_1 | dm2_1_0 | rj1out; //2209 = combine(impl w|only 1 inp has strand) wire [′NUMST*(′K+1)−1:0] ok2 =dm2_0_0 | dm2_1_1; //2208 = combine(impl w|only 1 imp has Strand) wire [′NUMST*(′K+1)−1:0] rj3; //2302 wire [′NUMST*(′K+1)−1:0] ok3; //2320 wire [1:0] okstat3; //2319 tube #(0,“ ”) rej3(rj3,rr3, rj2, {flush,flush,(~freeze)|flush],,clk); //2301, = rej3 tube tube #(0,“ ”) cmp3(ok3,ro3, ok2, {flush,flush,(~freeze)|flush},okstat3,clk); //2310 = cmp3 tube reg flag; //2317 // following always behavior implemented by logic 2318 // with inputs okstat3 2319 and initialize 5002 // producing output flag 2317 always @(posedge clk) begin if (initialize == 1) begin flag <= 0; end else if (okstat3 != 0) begin flag < =1; end end wire [′NUMST*(′K+1)−1:0] rj3ok; //2307 wire [′NUMST*(′K+1)−1:0] rj3rj; //2306 demux dmxrj(rj3ok, rj3rj, rj3, flag); //2305 = dmxrj demux wire [′NUMST*(′K+1)−1:0] ok3ok =0k3 | rj3ok; //2308 = combine(impl w|only 1 imp has strand) tube #(0,“ ”) cmp4(ok4,ro4, ok3ok,{flush,flush,(~freeze)|flush},,clk); //2410 = cmp4 tube //following combines require function calls in simulation //since multiple strands may be involved always @(rj3rj or rr3 or rr2 or rrl or ro4 or ro3) begin rrcomb = rj3rj; rrcomb = cmp4.combine(rr3,rrcomb); rrcomb = cmp4.combine(rr2,rrcomb); rrcomb = cmp4.combine(rr1,rrcomb); rrcomb = cmp4.combine(ro4,rrcomb); rrcomb = cmp4.combine(ro3,rrcomb); end endmodule module heirarchy(ok4,st,initialize,forcepipe,freeze,flush,ok4in,clk); //1000 output ok4; //200 input st; //5010-5012 input initialize; //5002 input forcepipe; //5001 input freeze; //5003 input flush; //5004 input ok4in; //300 input clk; wire [′NUMST*(′K+1)−1:0] ok4; wire [2:0] st; wire initialize; wire forcepipe; wire freeze; wire flush; wire [′NUMST*(′K+1)−1:0] ok4in; wire clk; initial //for simulation begin t4.t = 0; t3.t = 0; t2.t = 0; t1.t = 0; t0.t = 0; mem.t =t4.initStrand('aw); end wire [′NUMST*(′K+1)−1:0] o5; //1560 wire [′NUMST*(′K+1)−1:0] o4; //1460 wire [′NUMST*(′K+1)−1:0] o3; //1360 wire [′NUMST*(′K+1)−1:0] o2; //1260 wire [′NUMST*(′K+1)−1:0] o1; //1160 wire [′NUMST*(′K+1)−1:0] o0; //1060 wire [′NUMST*(′K+1)−1:0] rt4; //1420 wire [′NUMST*(′K+1)−1:0] rt3; //1320 wire [′NUMST*(′K+1)−1:0] rt2; //1220 wire [′NUMST*(′K+1)−1:0] rt1; //1120 wire [′NUMST*(′K+1)−1:0] rt0; //1020 reg [′NUMST*(′K+1)−1:0] rcomb; //3020 tube #0,“ ”) mem(o5,,rcomb,(2′b00,initialize),,clk); //3000 = mem tube wire s4,s3,s2,s1,s0; //1440,1340,1240,1140,1040 wire c4,c3,c2,c1,c0; //1450,1350,1250,1150,1050 //following nine lines part of logic 4000 wire z3 = (!s3)&&(!c3); wire z2 = (!s2)&&(!c2); wire z1 = (!s1)&&(!c1); wire z0 = (!s0)&&(!c0); wire f0 = 1; wire f1 = c0; wire f2 = s0&&z1; wire f3 = c0&&cl&&z2; wire f4 = s0&&cl&&z2&&z3; tube #(4,“ ”) t4(o4,rt4,o5,{(~freeze)&forcepipe|flush,(~freeze)&s4|flush, (~freeze)&f4|flush},{s4,c4},clk); //1410 = t4 tube tube #(3,“ ”) t3(o3,rt3,o4,{(~freeze)&forcepipe|flush,(~freeze)&s3|flush, (~freeze)&f3fflush},{s3,c3},clk); //1310 = t3 tube tube #(2,“ ”) t2(o2,rt2,o3,{(~freeze)&forcepipe|flush,(~freeze)&s2|flush, (~freeze)&f2|flush},{s2,c2},clk); //1210 = t2 tube tube #(1,“ ”) t1(o1,rt1,o2,{(~freeze)&forcepipe|flush,(~freeze)&s1|flush, (~freeze)&fl|flush},{sl,c1},clk); //1110 = t1 tube tube #(0,“ ”) t0(o0,rt0,o1,1(~freeze)&forcepipe|flush,(~freeze)&s0|flush, (~freeze)&f0|flush},{s0,c0},clk); //1010 = t0 tube wire [′NUMST*(′K+1)−1:0] rrcomb; //3020 compare comp(ok4,rrcomb,o0,st,initialize,freeze,flush,clk); //2000 = earlier “compare” module //following combines require function calls in simulation //since multiple strands may be involved always @(ok4in or rt4 or rt3 or rt2 or rt1 or rt0 or rrcomb) begin rcomb = t4.combine(rt4,ok4in); rcomb = t4.combine(rt3,rcomb); rcomb = t4.combine(rt2,rcomb); rcomb = t4.combine(rt1,rcomb); rcomb = t4.combine(rt0,rcomb); rcomb = t4.combine(rrcomb,rcomb); end endmodule // following simulates all possible starting (st) and ending (tries) addresses // for each such case, verify the correct (and only those correct) strands // appear in sequential order module test; integer st; reg initialize; reg forcepipe; reg freeze; reg flush; reg clk; wire [′NUMST*(′K+1)−1:0] ok4; heirarchy h(ok4, st[2:0],initialize,forcepipe,freeze,flush,ok4,clk) ; reg [′NUMST*(′K+1)−1:0] ok4copy; integer ok4predict,ok4actual; integer numwrong; initial numwrong = 0; always @(posedge clk) begin ok4copy = h.t4.compress(ok4); if (h.t4.getTubePop(ok4copY) == 0) ok4predict =st; else begin ok4actual =((1<<′K)−1) & h.t4.getStrand(ok4copy,0); $write(ok4actual,“ ”,ok4predict,“ ”); if (ok4actua1 !=ok4predict) begin $write(“WRONG”); numwrong = numwrong + 1; end $display(“ ”); ok4predict = ok4predict + 1; end end initial clk=0; always #50 clk=~Clk; integer i; integer starttime; // uncomment to teat freezing pipeline // always @(posedge clk) // begin // #1 // if (($time-starttime>2200)&($time−starttime<=2500)) // freeze = 1; // else // freeze = 0; // end integer tries; initial begin flush = 0; freeze = 0; initialize ft 0; forcepipe = 0; for (st = 0; st<′NUMST; st+=t+1) begin for (tries=st; tries<′NUMST; tries = tries + 1) begin @(posedge clk) #0; starttime = $time; $display(“st=”,st,“ tries=”,tries); initialize = 1; @(posedge clk) #0; initialize = 0; for (=′aw−1; i>=3; i+=i−1) begin forcepipe =st[i]; @(posedge clk) #0; end forcepipe = 0; wait(ok4actual===tries); flush <= 1; @(posedge clk) #0; ok4actual =′bx; @(posedge clk) #0; @(posedge clk) #0; @(posedge clk) #0; flush <= 0; @(posedge clk) #0; @(posedge clk) #0; //$stop; end end $display(“numwrong=”,numwrong); $finish; end endmodule
(80) TABLE-US-00009 Appendix 2: Recursive C Simulation of a 5-bit DNA Memory Hierarchy #include <stdio.h> #include <stdlib.h> #include <math.h> //singrecur.c recursive functional def of DNA memory hierarchy with 5-bit addr // little endian zero origin notation // uses a bitset to represent tube contents. // 0x00000001 is tube that contains strand with address 0 // 0x80000000 is tube that contains strand with address 0xlf // 0xffffffff is tube that contains all strands (addresses 0 ... 0xlf) int aw; long double awscale; //ratio is a real slightly less than 1.0 that when shifted over 2.sup.∧aw bits //acts as mask for portion of tube with bit k==0 to separate from //portion where bit k==1 (works because bitset representation is ordered, //even though a biochemical tube isn't) long double ratio(int k) { long double p; p = pow(2,pow(2,k)); return p/(p+1); } //mask the low part that stays in the tube on a separate long long L(long long t, int k) { long long mask; mask = ((long long) floor((1--ratio(k))*awscale)); return t & mask; } //mask the high part that leaves the tube on a separate long long H(long long t, int k) { long long mask; mask = ((long long) floor(ratio(k)*awscale)); return t & mask; } //the mod function (which in actual imp might be computed by logic) int f(int x, int k) ( return ((x+k)%(1<<k))==0; } //count how many strands in tube int countbit(long long x) ( int i,c=0; for (i=0; i<64; i ++) ( if (x&(1LL<<i)) c++; } return c; } //initialize tubes long long initt(int x, int k, long long y) ( if (k < −x) return 0; else if (x == 1−aw) return y; else if (x == 1−k) return L(initt(x−1,k+1,y),k+1); else if (x == 1−k) return H(initt(x−1,k,y),k); else return initt(x−1,k,y); } //recursive definition of pipeline //compared to actual implementation, very costly because //naive non-tail recursion recomputes the same stuff over and over long long t(int x, int k, long long y) { //printf(″t %d %d\n″,x,k); if (k>aw) return 0; else if (x <= 0) return initt(x,k,y); else if (countbit(t(x−1,k+1,Y)) > (1<<(k+1)) ) return L(t(x−1,k+1,y),k+1); else if (f(x−1,k+1)) return t(x−1,k+1,y); else if (!f(x−1,k)) return t(x−1,k,y); else if (countbit(t(x−1,k,y)) > (1<<k) ) return H(t(x−1,k,y),k); else return 0; } //for each cycle, print // t_−1, result singleton set output in correct order // t_0, set with up to two strands // . . . // t_4, set with up to 32 strands int main( ) { long long yy; int x; aw = 5; awscale = pow(2,pow(2,aw)); yy = ((long long) (awscale−1)); for (x=1−aw; x<=(1<<aw); x++) { printf(“%811x ”,t(x,−1,yy)); printf(“%811x ”,t(x,0,Yy)); printf(“%811x ”,t(x,1,yy)); printf(“%811x ”,t(x,2,yy)); printf(“%811x ”,t(x,3,yy)); printf(“%811x\n”,t(x,4,yy)); } return 0; } /* here is the correct output of this program: 0 0 0 0 0 ffffffff 0 0 0 0 ffff ffff0000 0 0 0 ff ff00 ffff0000 0 0 f f0 ff00 ffff0000 0 3 c f0 ff00 ffff0000 1 2 c f0 ff00 ffff0000 2 c 0 f0 ff00 ffff0000 4 8 f0 0 ff00 ffff0000 8 30 c0 0 ff00 ffff0000 10 20 c0 0 ff00 ffff0000 20 c0 0 ff00 0 ffff0000 40 80 100 1000 0 ffff0000 80 300 c00 f000 0 ffff0000 100 200 c00 f000 0 ffff0000 200 c00 0 f000 0 ffff0000 400 800 f000 0 0 ffff0000 800 3000 t000 0 0 fff10000 1000 2000 c000 0 ffff0000 0 2000 c000 0 ff0000 ff000000 0 4000 8000 f0000 f00000 ff000000 0 8000 30000 c0000 f00000 ff000000 0 10000 20000 c0000 f00000 ff000000 0 20000 c0000 0 f00000 ff000000 0 40000 80000 f00000 0 ff000000 0 80000 300000 c00000 0 ff000000 0 100000 200000 c00000 0 ff000000 0 200000 c00000 0 ff000000 0 0 400000 800000 f000000 f0000000 0 0 800000 3000000 c000000 f0000000 0 0 1000000 2000000 c000000 f0000000 0 0 2000000 c000000 0 f0000000 0 0 4000000 8000000 f0000000 0 0 0 8000000 30000000 c0000000 0 0 ffffffff 10000000 20000000 c0000000 0 ffff ffff0000 20000000 c0000000 0 ff ff00 ffff0000 40000000 80000000 f f0 ff00 ffff0000 80000000 3 c f0 ff00 ffff0000 after five (aw) cycles, the addresses start to appear in sequential order 0 (1), 1 (2), 2 (4), 3 (8), 4 (10), 5 (20), . . . 31 (80000000) */
(81) TABLE-US-00010 Appendix 3: C Programs that Print “sc” Patterns for DNA Memory Hierarchy ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc1.c similar to DNA23 poster, except // only prints “s”,“o” instead of doing separate, combine // unlike DNA23,comment out “clk< . . .” part of if // this has effect of repeating after 2.sup.∧n cycles instead of quitting // clk starts at 0 has similar role as x starts at 1−n in later pipeinc*x.c // n is same as aw in Verilog of appendix 1 // unlike most later pipeinc*x.c programs, this uses // little endian ONE origin tube numbers // this makes result appear in t_0 instead of t_−1 // (note these comments use _ to indicate subscripts) int main( ) { int clk,k,i,n,separatePos,combinePos; int iter; scanf(“%d”,&n); iter = (1<<n) +n; for (clk=0; clk<=iter-2; clk=clk+1) { for (k=1; k<=n; k=k+1) { for (i=0; i<=iter; i=i+1) {separatePos = n−k+i*(1<<k); combinePos = (1<<(k−1))+separatePos; if ((separatePos == clk)||(combinePos == clk)) break; } if (separatePos==clk)//&&(clk<iter-(1<<(k−1)))) printf(“s”); //separate(t_k,t_k−1,t_k,t k=1); else if (combinePos==clk) //&i(clk<=iter-(1<(k−1)))) printf(“c”); //combine(t_k−1,t_k); else printf(“ ”); } printf(“\n”); } } ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include >stdlib.h> #include <math.h> // pipeinc2x.c same as pipeinc1.c except // x starts at 1−n plays same as clk starts at 0 int main( ) { int x,k,i,n,SeparatePos,combinePos; int iter; scanf(“%d”,&n); . iter = (1<<n) +n; for (x=1−n; x<=iter−2+1−n; x=x+1) { for (k=1; k>=n; k=k+1) { for (i=0; i<=iter; i=i+1) {separatePos = n-k+i*(1<<k)+1−n; combinePos = (1<<(k−1))+separatePos; if ((separatePos == x)||(combinePos == x)) break; } if (separatePos==x) printf(“s”); //separate(t_k,t_k−1,t_k,t_k−1); else if (combinePos==x) printf(“c”); //combine(t_k−1,t_k); else printf(“ ”); } printf(“\n”); } } ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc3x.c same as pipeinc2x.c except // little endian ZERO origin // separatePos,combinePos replaced with mod calculation int main( ) { int x,k,i,n; int iter; scanf(“%d”,&n); iter = (1<<n)+n; for (x=1-n; x<=iter-l-n; x=x+1) {//printf(“%5d”,x); for (k=0; k<=n-1; k=k+1) { if ((x+k)%(1<<(k+1))==0) printf(“s”); //separate(t_k,t_k−1,t_k,t_k−1); else if ((x+k)%(1<<(k))==0) printf(“c”); //combine(t_k−1,t_k); else printf(“ ”); } printf(“\n”); } } ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc3xfun.c same as pipeinc3x.c except // uses f_function to encapsulate mod calculation int f(int x, int k) { return ((x+k)%(1<<(k)))==0; } int main( ) { int x,k,i,n; int iter; scanf(“%d”i&n); iter = (1<<n)+n; for (x=1-n; x<=iter-l-n; x=x+1) { //printf(“%5d ”,x); for (k=0; k<=−1; k=k+1) { if (f(x−1,k+1)) //((x+k)%(1<<(k+1))==0) printf(“s”); //separate(t k,t k−1,t_k,t_k−1); else if (f(x,k)) //((x+k)%(1<(k))==0) printf(“c”); //combine(t_k−1,t_k); else printf(“ ”); } printf(“\n”); } } ////////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc4xfun.c same as pipeinc3xfun.c except // logic expressed in terms of f_k and s_k int f_function(int x, int k) { return ((x+k)%(1<<(k)))==0; } int main( ) { int x,k,i,n,separatePos,combinePos; int iter; int f[100],s[100]; scanf(“%d”,&n); iter = (1<<n)+n; for (x=1−n; x<=iter−l−n; x=x+1) { //printf(“%5d “,x); for (k=0; k<=n-1; k=k+1) { f[k] = f_function(x,k); s[k] =f function(x−1,k+1); if (s[k]) //(f(x−1,k+1)) printf(“s”); //separate(t_k,t_k−1,t_k,t_k−1); else if (f[k]&&(!s[k])) //(f(X,k)) printf(“c”); //combine(t_k−1,t_k); else printf(“ ”); } printf(“\n”); } } /////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc5xfun.c same as pipeinc4xfun.c except // s_k (full occupancy of t_k) computed from f_k+1 in prey cyc // needs initial fn; since not reset final pipe stages differ // decision tests f_k then USeS s_k to decide “s” or “c” int f_function(int x, int k) { return ((x+k)%(1<<(k)))==0; } int main( ) { int x,k,n; int iter; int f[100],s[100]; scanf(“%d”,&n); iter = (1<<n)+n; for (k==0; k<=n−1; kk+1) f[k] = 0==1; f[n] = 1==1; for (x=1−n; x<=iter-l−n; x=x+1) { //printf(“%5d ”,x); for (k=0; k<=n-1; k=+1) { s[k] = f[k+1]; f[k] = f function(x,k); if (f[k]) { if (s[k]) printf(“s”); //separate(t_k,t_k−1,t_k,t_k); else printf(“c”); //combine(t_k−1,t_k); } else printf(“ ”); } printf(“\n”); f[n] = 0; } } /////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc6xfunsc.c same as pipeinc5xfun.c except // s_i and c_i calculated as in FIG. 6, but without force int f_function(int x, int k) { return ((x+k)%(1<<(k)))==0; ) int main( ) { int x,k,n; int iter; int f[100],s[100],c[100]; scanf(“%d”,&n); iter = (1<<n)+n; for (k=0; k<=n-1; k=k+1) { f[k] = 0==1; s[k] = 0==1; c[k] = 0==1; } f[n] = 1==1; s[n] = 1==1; for (x=1−n; x<=iter−l−n; x=x+1) { //printf(“%5d ”,k); for (k=0; k<=n−1; k=k+1) {c[k] = s[k] || ((!f[k])&&c[k]); s[k] = f [k+1]; f[k] = f_function(x,k); if (f[k]) { if (s[k]) printf(“s”); //separate(t_k,t_k−1,t_k,t_k); else printf(“c”); //combine(t_k−1,t_k); } else printf(“ ”); } for (k=0; k<=n−1; k=k+1) printf(“%d%d ”,s[k],c[k]); printf(“\n”); f[n] =0; } } /////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.b> #include <math.h> // pipeinc6xlogeqn.c same as pipeinc6xfunsc.c except // output intended to print logic equations like those in Table 3 // input n=4 prints logic equations up to f15 // input n=5 prints logic equations up to f31 // input n=6 prints logic equations up to f63, etc. // int f_function(int x, int k) {return ((x+k)%(1<<(k)))==0; } int main( ) { int i,x,k,n; int iter; int f[100],s[100],c[100]; scanf(“%d”,&n); iter = (1<<n)+n; for (k=0; k<=n−1; k=k+1) { f[k] = 0==1 s[k] = 0==1; c[k] = 0==1; } f[n] = 1==1; s[n] = 1==1; for (x=1−n; x<=iter−1−n; x=x+1) {i = iter−n − x; if (x>0) printf(“f%d=”,i); for (k=0; k<=n−1; k=k+1) { c[k] =s(k) || ((!f[k])&&c(k+); s[k] = f[k+1]; f[k] = f_function(x,k); if (s[k]) { if ((k<i)&&(x>0)) printf(“s%d”,k); } else if (c[k]) { if ((k<i)&&(x>0)) printf(“c%d”,k); } else { if ((k<i)&&(x>0)) printf(“z%d”,k); } } for (k=n; k<=iter−n; k=k+1) { if ((k<i)&&(x>0)) printf(“z%d”,k); } if (x>0) printf(“\n”); f[n] = 0; } } /////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc7xfunsc.c same as pipeinc6xfun.c except // s[ ] and c[ ] computed via recurrence/state machine method // f[ ] computed via logic equations (up to n=5) // if statements similar to pipeinc4xfun.c int f_function(int x, int k) {return ((x+k)%(1<<(k)))==0; ) int main( ) { int x,k,n; int iter; int f[100],s[100],c[100],z[100]; scanf(“%d”,&n); iter = (1<<n)+n; for (k=0; k<=n-1; k=k+1) { f[k] = 0==1 s[k] = 0==1 c[k] = 0==1; } f[n] = 1==1; for (x=1-n; x<=iter−1−n; x=x+1) { printf(“%5d ”,x); for (k=0; k<=n-1; k=k+1) {c[k] = s[k] || ((!f[k])&&c[k]); s[k] = s[k+1]||f[k+1]; z [1] = (!s[1]) && (!c[1]); z [2] = (!s[2]) && (!c[2]); z [3] = (!s[3]) && (!c[3]); if (k==0) f[0] = 1== 1; if (k==1) f[1] = c[0]; if (k==2) f[2] = s[0]&&z[1]; if (k==3) f[3] - c[0]&&c[1]&&z[2]; if (k==4) f[4] = s[0]&&C[1]&&z[2]&&z[3]; if (s[k]) printf(“s”); //separate(t_k,t_k−1,t_k,t_k); if ((!s[k])&&f[k]) printf(“c”); //combine(t_k−1,t_k); if ((!s[k])&&(!f[k])) printf(“ ”); } for (k=0; k<=n−1; k=k+1) printf(“ %d%d”,s[k],c[k]); for (k=0; k<=n−1; k=k+1) printf(“ %d”,f[k]); printf(“\n”); f[n] =0; } } /////////////////////////////////////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> #include <math.h> // pipeinc8xfunsc.c same as pipeinc7xfun.c except // allows initialization of high order three bits // by force technique (as in FIGS. 4-5) for s_i and c_i int f_funttion(int x, int k) { return ((x+k)%(1<<(k)))==0; } int main( ) { int x,k,n; int iter; int f[100],s[100],c[100],z[100]; int xinit,force,force4,force3,force2; scanf(“%d”,&n); scanf(“%d”,&xinit); force4 = 1&(xinit>>4); force3 = 1&(xinit>>3); force2 = 1&(xinit>>2); printf(“highorder=%d%d%d\n”,force4,force3,force2); iter = (1<<n)+n; for (k=0; k<=n−1; k=k+1) { f[k] = 0==1; s[k] = 0==1; c[k] = 0==1; } f[n] = 1==1; for (x=xinit+1−n; x<=iter−1−n; x=x+1) { printf(“%5d ”,x); if (x==xinit−3) force = force4; else if (x==xinit−2) force = force3; else if (x==xinit−1) force = force2; else force = 0; for (k=0; k<=n−1; k=k+1) { c(k) = (s[k] && (force==0)) || ((!f[k])&&c[k]); s[k] = s[k+1]||f[k+1]; z[1] = (!s[1])&&(!c[1]); z[2] = (!s[2])&&(!c[2]); z[3] = (!5[3])&&(!c(3)); if (k==0) f[0] = 1==1 if (k==1) f[1] = c[0]; if (k==2) f[2] = s[0]&&z[1]; if (k==3) f[3] = s[0]&&c[1]%&&z[2] if (k==4) f[4] = s[0]&&c[1]&&z[2]&&z[3]; if (s[k]) printf(“8”); //teparate(t_k,t_k−1,t_k,t_k); if ((!s[k])&&f[k]) printf (“c”); //combine(t_k−1,t_k); if ((!s[k]) && (!f[k])) printf (“ ”) ; } for (k=0; k<=n−1; k=k+1) printf(“ %d%d”, s[k] , c[k]); for (k=0; k<=n−1; k=k+1) ' printf(“ %d”, f [k] ) ; printf(“ force=%d\n”, force); f[n] = 0; } }
(82) TABLE-US-00011 Appendix 3: Exhaustive Java Simulation of Pipeline Initialization for 11-bit Address import java.lang.Integer; public class StkPlayllc( //note: capital S3 and S5 to avoid naming conflict with Stickx static boolean s0,s1,52,S3,s4,S5,s6,s7,s8,s9,s10; static boolean c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10; static boolean z1,z2,z3,z4,z5,z6,z7,z8,z9; static boolean f1,f2,f3,f4,f5,f6,f7,f8,f9,f10; static int aw, Mt, Mts, M, temp, PCIR; //****sticker modified to have tubePop (except staple) 5/27/18 //it current_read_pos = 0; //boolean read_safely = true; static boolean produce_listing = true; static int 1 = 2; //form.user_1.value; static int k = 4; //form.user_k.value; static int numTubes = 4;//form.user_numTubes.value; static String user_fmt = “2d1b1b”; //static String alpha = “abcdefghijklmnopqrstuvwxyz”; static int numStrands = 0; static int maxStrands = 3600000; //static String[ ] s3 = new String[maxStrands]; //static String[ ] s5 = new String[maxStrands]; static into strand = new int[maxStrands]; static int[ ] tubeNum = new int[maxStrands]; static int[ ] tubePop = new int[maxStrands]; // 5/27/18 faster for Ghosal-Sakar public static void mywriteln(String s) { System.out.println(s); } public static void myerr (String s) { mywriteln(s); } public static void mywrite(String s) { System.out.print(s); } // simulated Pascal strings public static String mycopy(String s, int posit, int len) ( //System.out.println(“posit =” +posit+“ len =”+len+“ s =”+s); if (posit < 1 || len < 0) return(“ ”); else if (posit+len > s.length()) return(s.substring(posit−1)); else return(s.substring(posit−1,posit+len−1)); } public static int mypos(String s1, String s2) { //if (s2 == “ ” && s1 != “ ”) //if (s2.equals(“ ”) && (!sl.equals(“ ”)) if (s2.1ength( ) == 0 && s1.length( ) != 0) return (0); else return(s2.index0f(s1) + 1); } public static String deblank(String s) { int i,posnb; posnb = −1; for (i=s.length( )−1; i >=0; i−−) { if (!(s.substring(i,i +1).equals(“ ”))) posnb = i; } if (posnb ! = −1) return(s.substring(posnb,s.length( ))); else return(s); } public static String shortenline(String line) { int posblank; posblank =mypos(“ ”, line); if (posblank ==0) posblank = line.length( ) + 1; return(mycopy(line, posblank+1, line.length( ))); } /* function to remove right blanks from line */ public static String trim(String line) /*string to be trimed*/ { int i, /*pos in string*/ nonbl ;/*pos of rightmost non-blank*/ nonbl = line.length( ); /*in case no blanks in string, don't trim*/ for (i = 1; i <= line.length({); i ++ ) { if (!(mycopy(line, i, 1).equals(“ ”))) nonbl = i; } return(mycopy(line, 1, nonbl)); } /*trim*/ public static int getK( ) { return k−0; } public static int getL( ) { return 1−0; } public static int getNumTubes( ) { return numTubes−0; } public static int getNumStrands( ) {int ii,count=0; for (i i=0; ii < numStrands; ii++) { if (tubeNum[ii] ! = −1) count++; } return (count); } public static int getTubePop(int i) { int ii; int count=0; if (i >=numTubes) mywriteln(“tube ” +i+“ too big”); return tubePop[i]; } public static String toBinary(int x, int k) { int i; String s =“ ”; int mask =1<<k; for (i = k−1; i>=0; i−−) { if ((x&(1<<i))! =0) s = s + “1”; else s = s + “0”; mask = mask >> 1; } return s; } public static String toReverseBinary(int x, int k) { int i; String s=“ ”; int mask = 1<<k; for (i =k−1; i >=0; i−−) { if ((x&(1<<i))! =0) s = “1” + s; else s = “0” + s; mask = mask >> 1; } return s; } public static String getfirstfmt(String fmt) { int posd = mypos(“d”, fmt); if (posd==0) posd = fmt.length( ); int posb = mypos(“b”, fmt); if (posb==0) posb = fmt.length( ); int posr = mypos(“r”, fmt); if (posr==0) posr = fmt.length( ); int posfmt = Math.min(Math.min(posd, posb), posr); return(mycopy(fmt, 1, posfmt)); } public static String formatConvert(int x, int k, String fmt) { if ((k <=0)||(fmt.length( )==0)) return “ ”; String firstfmt =getfirstfmt(fmt); Integer firstk =new Integer(mycopy(firstfmt, 1, firstfmt.length( )−1)); String firstx = “ ” +(x>>(k−firstk)); if (mycopy(firstfmt,firstfmt.length( ),1).equals(“b”)) firstx = toBinary(new Integer(firstx),firStk); else if (mycopy(firstfmt,firstfmt.length (),1).equals(“r”)) firstx = toReverseBinary(new Integer(firstx),firstk); String restConvert = “ ”+formatConvert(x&((1<<(k−firstk))−1), k−firstk, mycopy(fmt, firstfmt.length( ) +1, fmt.length( ))); if (restConvert.length( ) == 0) return “ ”+firstx; else return “ ”+firstx +“_” +restConvert; } public static String getTube(int i) { String s=“ ”; int ii; String convertedStrand; if (i>=numTubes) mywriteln(“tube ” +i +“ too big”); else for (ii = 0; ii < numStrands; ii++) {if (tubeNum[ii]==i) {convertedStrand = formatConvert(strand[ii],k,user_fmt); if (s.length( )==0) s =“ ” + convertedStrand; else s =s + “,” +convertedStrand; } } return s; } public static String tubeToString( ) {int i; String s =“ ”; for (i=0; i <numTubes i ++) s = s + “ ” + i + “:{” + getTube(i) + “} ”; return s; } public static void listOn( ) { produce_listing = true; //form.list_button.value =“List Off”; } public static void listOff( ) { produce_listing = false; //form.1ist_button.value =“List On”; } public static void displayAfter( ) { if (produce_listing) mywriteln(tubeToString( )); } public static void display( ) { mywriteln(“ ”+tubeToString( )); } public static void init(int i) { int ii; if ( i>numTubes) mywriteln(“i too big”); else if ((1<<1) > maxStrands-numStrands) myerr(“exceed maxStrands”); else { for (ii=numStrands; ii < numStrands +(1<<l); ii ++) { tubeNum[ii] = i; strand[ii] = ii-numStrands; } numStrands += 1<<1; tubePop[i] += 1<<1; //5/27/18 } if (produce_listing) mywrite(“init”); displayAfter( ); } public static void initCustom(int i; int v) { if (i >numTubes) mywriteln(“i too big”); else if (v>=(1<<k)) mywriteln(“v too big”); else { tubeNum[numStrands] = i; strand[numStrands] = v; numStrands += 1; tubePop[i] += 1; // 5/27/18 if (numStrands >= maxStrands) myerr(“exceed maxStrands”); } if (produce_listing) mywrite(“cust”); displayAfter( ); } public static void set(int i, int kk) { int ii; if (kk>=k) mywriteln(“k too big”); int temp = 1<<kk; if (i>=numTubes) mywriteln(“tube ” +i+“ too big”); else for (ii=0; ii < numStrands; ii++) { if (tubeNum[ii] == i) strand[ii] |= temp; } if (produce_listing) mywrite(“set ”); displayAfter( ); } public static void clear(int i; int kk) { int ii; if (kk>=k) mywriteln(“k too big”); int temp = ~(1<<kk) ; if (i>=numTubes) mywriteln(“tube ”+i+“ too big”); else for (ii=0; ii < numStrands; ii++) { if (tubeNum[ii] == i) strand[ii] &= temp; } if (produce_listing) mywrite(“clr ”); displayAfter( ); } public static void separate(int i, int j, int k) { separate3(i, j, j, k); } public static void separate3(int i1, int i0, int j, int kk) { int ii; if (kk>=k) mywriteln(“k too big”); int temp = 1<<kk; if ((i1>=numTubes) || (i0>numTubes) || (j>numTubes)) mywriteln(“tube ”+i1+“ or ”+i0+“ or ”+j+“ too big”); else for (ii=0; ii < numStrands; ii++) {if (tubeNum[ii] == j) if ((strand[ii]+&temp) == temp) {tubeNum[ii] = i1; tubePop[j]−−; tubePop[i1]++; } // 5/27/18 else {tubeNum[ii] = i0; tubePop+j+−−; tubePop[i0]++; } // 5/27/18 } if (produce_listing) mywrite(“sep ”); displayAfter( ); } public static void discard(int i) { int ii; if (i>=numTubes) mywriteln(“tube ”+i+“ too big”); else for (ii=0; ii < numStrands; ii++) { if (tubeNum[ii] == i) tubeNum[ii] = −1; } tubePop[i] = 0; // 5/27/18 if (produce_listing) mywrite(“dis ”); displayAfter( ); } public static int removeOneStrand(int i) { int ii,v=−1; if (i>=numTubes) mywriteln(“tube ”+i+“ too big”); else { for (ii = 0; ii < numStrands; ii++) { if (tubeNum[ii]==i) { v = strand[ii]; tubeNum[ii] = −1; tubePop[i]−−; // 5/27/8 break; } } } return v; } public static void combine(int i, int j) { int ii; if ((i>=numTubes) || (j>numTubes)) mywriteln(“tube ”+i+“ or ”+j+“ too big”); else for (ii=0; ii < numStrands; ii++) { if (tubeNum[ii] == j) tubeNum[ii] = i; } tubePop[i] += tubePop[j]; // 5/27/18 tubePop[j] = 0; if (produce_listing) mywrite(“comb”); displayAfter( ); } public static void split(int i, int j) { int ii; if ((i>=numTubes) || (j>numTubes)) mywriteln(“tube ”+i+“ or ”+j+“ too big”); else for (ii=0; ii < numStrands; ii++) {if ((tubeNum[ii] == j)&&(Math.random( )>0.5)) {tubeNum[ii] = i; tubePop[j]−−; tubePop[i]++;} //5/27/18 } if (produce_listing) myWrite(“split”); displayAfter( ); } public static void splitDeterministic(int i, int j) { int ii; boolean odd=false; if ((i>=numTubes) || (j>numTubes)) mywriteln(“tube ”+i+″ or ″+j+″ too big″); else for (ii=0; ii < numStrands; ii++) { if (tubeNum[ii] == j) . { if (odd) (tubeNum[ii] = i; tubePop[j]−−; tubePop[i]++;) //5/27/18 odd = !odd;} } if (produce_listing) mywrite(“splitDet”); displayAfter( ); } //****end of stickers with tubePop 5/27/18 public static void xortest( ) { int i; System.out.println(“Java Extended Stickers: xor”); produce_listing = true; 1 = 3; k = 5; numTubes = 4; user_fmt = “2d3d”; discard(0); init(0); //tube0=k-bit strands;1 bits init'ed;k-1 bits=0\n”; separate(1,0,0); //if bit0==0 stay tube0;else tube1\n”; separate(3,1,1); //if bit1==0 stay tubel;else tube3\n”; separate(2,0,1); //if bit1==0 stay tube0;else tube2\n”; combine(1,2); //pour tube 2 into 1\n”; for (i-getL( );i<=getL( )+1;i++)//javascript loop example\n”; set(1,i); //sets bits 1,1+1 (ie2,3)\n”; combine(0,3); //pour tube 3 into 0\n”; combine(0,1); //pour tube 1 into 0\n”; mywriteln(“result: ”+getTube(0)); mywriteln(“number: ”+getTubePop(0)); } public static int getnN(int x) { int i,nN; nN=0; for (i=1; i<=aw-2; i++) //don't do MSB { if ((x&(1<<i)) != 0) { if ((i+(((1<<i)-−1)&x)) >= (1<<i) } nN = i; } } return nN; } public static void gennN(int start) { int nN,iI; nN = getnN(start); //mywriteln(form,“start nN=”+nN); for (iI = 1; iI<=(nN+1−(1<<nN)+((1<<nN)−1&start)); iI++) (//mywrite(form,start+“ iI=”+ii+“ ”); if (iI == 1) combine(Mts+nN,nN+1); //mywriteln(form,“combine(”+(0+Mts+nN)+“,”+(l+nN)+“)”); else separate3(2+nN−iI,Mts+nN−iI+1,Mts+nN−iI+2,2+nN−iI); //mywriteln(form,“separate3(”+(2+nN−iI)+“,”+ //(0+Mts+nN−iI+1)+“,”+(0+Mts+nN−iI+2)+“,”+(2+nN−iI)+“)”); } } public static void printnN(int start) { int nN,iI; nN = getnN(start.); mywriteln(“start nN=”+nN); for (i{ = 1; ii<=(nN+1−(1<<nN)+((1<<nN)−1&start)); iI++) (mywrite(start+“ iI=”+iI+“ ”); if (ii == 1) //Combine(Hts+nN,nN+1); mywriteln(“combine(”+(0+Mts+nN)+“,”+(1+nN)+“)”); else //separate3(2+nN−iI,Mts+nN−iI+1,Mts+nN−iI+2,2+nN-iI); mywriteln(“separate3(”+(2+nN−iI)+“,”+ (0+Mts+nN−iI+1)+0,0+(0+Mts+nN−iI+2)+“,”+(2+nN−iI)+”)0); } } public static void fetchpipe(int addr) {int i; combine(Mts+aw−1,M); for (i=aw−1; i>1; i=i−1) fseparate(temp,addr,i/*+aw*/); if (getTubePop(temp)>0) separate3(Mts+i−1,M,Mts+i,i); . else separate3(Mt+i,Mts+i−1,Mts+i,i); combine(addr,temp); } separate(temp,addr,1/*+aw*/); //maybe redund to extra iteration above if (getTubePop(temp)>0) separate3(Mts,M,Mts+1,1); else separate3(Mt+1,Mts,Mts+1,1); combine(addr,temp); separate(temp,addr,0/*+aw*/); if (getTubePop(temp)>0) separate3(Mt+0,M,Mts+0,0); combine(addr,temp); } public static void flipTubeState(boolean f, boolean s, int i) {if (i==0) { if (s0) {//mywrite(form,“S0”); separate3(Mt+0,temppipe /*2*Mts*/,Mts+0,0);} else {//mywrite(form,“C0”); combine(temppipe /*2*Mts*/,Mt+0);} } else {if (f) {if (s) {//mywrite(form,“S”+i+“ ”); separate3(Mt+i, Mts+i−1, Mts+i, i);} else {//mywrite(form,“C”+i+“ ”); combine(Mts+i−1,Mt+i);} } } } public static void iter () { s0 = getTubePop(Mts+0)>0; s1 = getTubePop(Mts+1)>0; s2 = getTubePop(Mts+2)>0; s3 = getTubePop(Mts+3)>0; s4 = getTubePop(Mts+4)>0; s5 = getTubePop(Mts+5)>0; s6 = getTubePop(Mts+6)>0; s7 = getTubePop(Mts+7)>0; s8 = getTubePop(Mts+8)>0; s9 = getTubePop(Mts+9)>0; s10 = getTubePop(Mts+10)>0; c0 = getTubePop(Mt+0)>0; c1 = getTubePop(Mt+1)>0; c2 = getTubePop(Mt+2)>0; c3 = getTubePop(Mt+3)>0; c4 = getTubePop(Mt+4)>0; c5 = getTubePop(Mt+5)>0; c6 = getTubePop(Mt+6)>0; c7 = getTubePop(Mt+7)>0; c8 = getTubePop(Mt+8)>0; c9 = getTubePOp(Mt+9)>0; c10 = getTubePop(Mt+10)>0; //mywriteln(form,“C0=“+c0+”; C1=“+c1+”; C2=“c2+”; C3=“+c3+”; C4=“*c4+”;”); //mywriteln(form,“S0=“+s0+”; S1=“+s1+”; S2=“+s2+”; S3=“+s3+”; S4=“+s4+”;”); //mywriteln(form,“f1=“+f1+”; f2=“+f2+”; f3=“+f3+”;f4=“+f4+”;)”); z1 = (!s1)&&(!c1); z2 = (!s2)&&(!c2); z3 = (!s3)&&(!c3); z4 = (!s4)&&(!c4); z5 = (!s5)&&(!c5); z6 = (!s6)&&(!c6); z7 = (!s7)&&(!c7); z8 = (!s8)&&(!c8); z9 = (!s9)&&(!c9); f1 = c0; f2 = s0&&z1; f3 = c0&&cl&&22; f4 = s0&&cl&&z2&&z3; f5 = c0&&sl&&z2&&z3&&z4; f6 = s0&&z1&&c2&&z3&&z4&&z5; f7 = c0&&cl&&c2&&z3&&z4&&z5&&z6; f8 = s0&&cl&&c2&&23&&24&&z5&&t6&&z7; f9 = c0&&sl&&c2&&z3&&z4&&z5&&z6&&z7&&z8; f10 = s0&&z1&&s2&&z3&&z4&&z5&&z6&&z7&&z8&&z9; flipTubeState(true,s0,0); flipTubeState(f1,s1,1); flipTubeState(f24s2,2); flipTubeState(f3,S3,3); flipTubeState(f4,s4,4); flipTubeState(f5,S5,5); flipTubeState(f6,s6,6); flipTubeState(f7,s7,7); flipTubeState(f8,58,8); flipTubeState(f9,s9,9); flipTubeState(f10,s10,10); } static iht temppipe, cmp0, cmp1, addr0, addr1; public static void comparePCIR( ) {int i; for (1=0; i<=3; i=i+1) ( combine(addr0,addr1); separate(addr1,addr0,i); if ( ((getTubePop(addr1)>0)!=(getTubePop(cmp1+i)>0)) && ((getTubePop(addr1)>0)||(getTubePop(addr0)>0)) ) { combine(M,cmp0+i); combine(M,cmp1+i); } else { separate3(cmp1+i+1,cmp0+i+1,cmp0+i,i+1); separate3(cmp1+i+1,cmp0+i+1,cmp1+i,i+1); } } if ((getTubePop(cmp0+4)>0)||(getTubePop(cmp1+4)>0)) { combine(PCIR,addr0); combine(PCIR,addr1); } combine(2*Mts,cmp0+4); combine(2*Mts,cmp1+4); separate3(cmp1+0,cmp0+0,temppipe,0); } public static void fetchpipeplay2(int addr) {int i; combine(Mts+aw−1,M); for (i=aw−1; 1>0; i=1−1) {separate(temp,addr,i/*+aw*/); if ((getTubePop(temp)>0)&&(i+>=4)) separate3(Mts+i−1,M,Mts+i,i); else separate3(Mt+i,Mts+i−1,Mts+i,i); combine(addr,temp); } } public static void fetchpipeplay(int addr) {int i; boolean 1b1=false, 1b2=false, 1b3=false, 1b4=false,allow=true; combine(Mts+aw−1,M); for (i=aw−1; 1>0; 1=1−1) {separate(tempiaddr,i/*+aw*/); if ((getTubePop(temp)>0)&&allow) {separate3(Mts+i−1,M,Mts+i,1); if (i>=8) 1b4 |= true; else if (i>=4) 1b3 |= true; else if (i>=2) 1b2 |= true; else if (i>=1) lbl 1= true; if ((i==4)&&1b4) allow=false; if ((i==3)&&1b3) allow=false; if ((i==2)&&1b2) allow=false; if ((i==1)&&1b1) allow=false; } else { separate3(Mt+i,Mts+i−1,Mts+i,i); 1b4 = false; 1b3 = false; 1b2 = false; 1b1 = false; } combine(addritemp); } if (allow) { separate(temp,addr,0/*+aw*/); if (getTubePop(temp)>0) separate3(Mt+0,M,Mts+0,0); combine(addr,temp); } System.out.println(allow+“ “+1b4+” “+1b3+” “+1b2+” ”+1b1); } public static void nletest( ) {int i,jj,iii,start; System.out.println(“Java Extended Stickers: NLE”); produce_listing = false; user_fmt = “lld”; aw = ll; l = aw; k = aw; numTubes = 2*aw+18; Mt = 0; Mts =aw; M = 2*aw+2; temp = 2*aw+1; PCIR = 2*aw+3; temppipe = 2*aw+4; addr0 = 2*aw+5; addr1 = 2*aw+6; cmp0 = 2*aw+7; cmp1 = 2*aw+12; init(Mts*2−1); double.avgdone=0.0,donetime=0,0; for (start=0;start<(1<<aw); start++) { for(i=0;i<=M;i++) if (i != 2*Mts−1) combine(2*Mts−1, i); discard(PCIR); initCustom(PCIR,start); System.out.print(start+“ ”); fetchpipeplay(PCIR); // ***** replace With fetchpipeplay2 for alternative combine(addr0,PCIR); donetime = 0.0; for(jj=start;jj<(1<<aw)+16;jj++) { iter( ); comparePCIR( ); if (((getTubePop(2*Mts)+start)==(1<<aw)) && (donetime==0.0)) {System.out.println(start+“ DONETIME=”+(0+jj−(1<<aw))); donetime =jj−(1<<aw); avgdone += donetime; //System.out.println(“AVGDONE=”+(avgdone/(Math.pow(2.0,aw)))); } } for(iii=0;iii<2*aw;iii++) { if (getTubePop(iii)>0) mywrite(“WRONG ”); } if ((getTubePop(2*Mts)+start) != (l<<aw)) mywriteln(“BADCOUNT ”+getTubePop(2*Mts)+“ ”+(0+getTubePop(2*Mts)+start)); display( ); } System.out.println(“AVGDONE=”+(avgdone/(Math.pow(2.0,aw)))); } public static void main(String [ ] arg) { nletest( ); } }