Research Topics

  1. Tests T5, T6, and T7 all test for a relaxation of write atomicity. Test T7 shows that numerous machines relax WA. No machine to date has failed T5 or T6. Why do the machines that fail test T7, never fail the logically equivalent tests T5 or T6?

  2. Program Order and Write Atomicity are completely independent logical concepts. Nothing prevents there being machines which obey one rule and not the other, or both rules, or neither rule. Tests done to date, however, show that any machine which obeys PO, also obeys WA. Why is this?

  3. On some machines Test 8 shows that during some periods of time different threads see operand A take on the same sequence of values. The period of time can extend for as long as 20 or so loop executions. On other machines these convoys of values do not appear. What is it in the hardware design that causes convoys to appear on some machines, but not on others?

       Convoys are of length 14 or 15:  A 4-way Sun Sparc 630 
       Convoys are of length 3:  A KSR-1 
       No convoys were visible:
         A NUMAchine 
         A 2-way Sun Sparc 20 
         A 2-way Sun Spark Ultra-2 
         A 2-way Intergraph TD-400 
  4. Is it desirable to standardize on one shared memory architecture? If so, what should it be? There are three major groups of behaviors seen so far, plus a couple of minor variations, plus more promised. Should it be as strong as possible, or as relaxed as possible? Is there any justification for an intermediate standard?

  5. Relaxing an architecture can lead to an improvement in machine performance. The effect, however, is reduced by an increased need to use atomic instructions in frequently executed routines at the heart of an operating system. What is the net performance benefit of relaxing an architecture?

  6. Extend the current model to more accurately model a real-life machine. Add durations to each event. Identify the maximum size of possible windows in which events occur late. Prove that any distinguishing path would necessarily overflow the largest possible window.

  7. Can a critical section routine be written which runs on a relaxed architecture machine? The answer is: yes. Any critical section routine can be modified to run on a machine whose only relaxation is to allow reads to occur before writes: after every store into an operand, just fetch the operand. The rule of CRR will then prevent subsequent reads from occurring early. So the question becomes: can a critical section routine be written which runs on a machine which relaxes CC1 or any order rules other than CWR.

Site Map

Last updated January 4, 2006.