Does Real Locality Exist?

After the post on computational locality, it is interesting to examine our understanding of physical locality.  There is a fascinating storyline in the history of physics.

Einstein is one of the greatest physicists.  However, he was always troubled by quantum mechanics whose results, unlike Newton mechanics, are inherently probabilistic rather than deterministic.   For example, his quote “God does not play dice with the universe” was actually a direct criticism.

The discovery of two-particle quantum entanglement gave him a chance to formulate his objection precisely.  In 1935, Einstein, Boris Podolsky and Nathan Rosen distributed the so-called EPR paradox.  They laid out four premises of a physics theory:

[Greenberger et al. 1990] state in EPR’s words.

  • (i) Perfect correlation: If the spins of particles 1 and 2 are measured along the same direction, then with certainty the outcomes will be found to be opposite.
  • (ii) Locality: “Since at the time the two systems no longer interact, no real change can take place in the second system in consequence of anything that may be done to the first system.”
  • (iii) Reality: “If, without in any way disturbing a system, we can predict with certainty the value of a physical quantity, then there exists an element of physical reality corresponding to this physical quantity.”
  • (iv) Completeness: “Every element of the physical reality must have a counterpart in the [complete] physical theory.”

For a two-particle entanglement, the measurement of particle 1 can cause no real change in particle 2.   Until the measurement, the states of particles 1 and 2 have no definite values from the theory of quantum mechanics.  Therefore, as a theory quantum mechanics is incomplete.

These objections were unresolved (and largely ignored) by physicists in the next fifty years.  A series of studies on Bell Inequality were made, but the experimental setups were open to criticism.

In late 1980s, researchers at University of Rochester especially Leonard Mandel, Professor of Physics and Optics, and his students followed on their studies on the quantum properties of light and invented a technique called parametric down-conversion to produce entangled photons.

Daniel Greenberger, while visitingVienna with Anton Zeilinger, found that a perfect correlation among three particles was enough to disprove EPR.  Michael Horne, back at Boston, discovered Mandel’s two-particle interference design based on a “folded diamond. ”

The paper by Greenberger et al. was published in 1990.  It shows that for 3 or more particle entanglement, the four EPR premises would derive contradictory results.  No theory that meets these four premises can explain the perfect correlation in such entanglements.  In the proof by Greenberger et al., (Section III, slightly more than 1 page), “the manipulation of an additional degree of freedom is essential to the exhibition of a contradiction.”

The contradiction shows that either locality or reality assumptions do not hold.  The combination of the two is now called “local realism.”

Scully et al. wrote that “In an ingenious experiment with [Zhe-Yu] Ou, Leonard utilized polarization entanglement for photon pairs produced in down conversion to achieve a violation of Bell’s inequality (i.e., local realism).”

I first heard about the story from the book by Aczel and taught the 1990 paper in the opening lecture of a graduate seminar in Spring 2005 on Modeling and Improving Large-Scale Program Behavior.

References

Greenberger, Daniel M., et al. “Bell’s theorem without inequalities.” Am. J. Phys 58.12 (1990): 1131-1143.

ROBERT J. SCULLY, MARLAN O. SCULLY, AND H. JEFF KIMBLE, “Leonard Mandel,” Biographical Memoirs: Volume 87,  The National Academies Press  (2005)

Zhe-Yu Ou and Leonard Mandel. Violation of Bell’s inequality and classical probability in a two-photon correlation experiment. Phys. Rev. Lett.61(1988):50.

Amir D. Aczel, Entanglement: The Greatest Mystery in Physics.  Random House, Inc. (2002)

 

Denning’s Definition of Locality

Here are three sources people can cite for the definition of locality by Peter Denning:

“The tendency for programs to cluster references to subsets of address space for extended periods is called the principle of locality” on page 143 in Peter J. Denning and Craig H. Martell. 2015. Great Principles of Computing. MIT Press

Locality is “the observed tendency of programs to cluster references to small subsets of their pages for extended intervals.” on page 23 in Peter J. Denning. 2005. The locality principle. Communications of ACM 48, 7 (2005), 19–24

Locality is “a pattern of computational behavior in which memory accesses are confined to locality sets for lengthy periods of time.” in an email from Denning,  June 26, 2016.

Given the domain name of this site, it is fitting to have the precise definition of the term here.

Locality has been discussed by others.

In their influential paper titled  Dynamic Storage Allocation: A Survey and Critical Review [ISMM 1995], Wilson and others wrote “Locality is very poorly understood, however; aside from making a few important general comments, we leave most issues of locality for future research.”

LCPC/CnC 2016 Location

The two workshops, LCPC and CnC, will be held at Hilton Garden Inn in the college town next to University of Rochester river campus (arts, sciences and engineering) and medical school:

Hilton Garden Inn
Rochester/University & Medical Center
30 Celebration Drive
Rochester, New York, 14620, USA

The LCPC Conference Group rate is $134 per night, not including tax (currently 14%).  Reservations of the conference rate must be received on or before Monday, September 5, 2016.  To reserve a room, use this link.

Local transportation.  The hotel (and the university) is about 4.2 miles from the Rochester International Airport (ROC).  The taxi fare is around $10.

ISMM Best Student Paper

An example of not only high-quality research but also collaboration between ECE and CS combining hardware support and program analysis. The conference is ACM SIGPLAN International Symposium on Memory Management http://conf.researchr.org/track/ismm-2016/ismm-2016-papers#program Here is the information about the award paper:

Hardware Support for Protective and Collaborative Cache Sharing 

Raj Parihar, Jacob Brock, Chen Ding and Michael C. Huang

Abstract: In shared environments and compute clouds, users are often un- related to each other. In such circumstances, an overall gain in throughput does not justify an individual loss. This paper presents a new cache management technique that allows conservative sharing to protect the cache occupancy for individual programs, yet enables full cache utilization whenever there is an opportunity to do so.

Rochester DandyHacks

3rd spring Hackathon, 120 students, 36 hours, 17 projects, CS and data science.  

Award winners:  http://dandyhacks2016.devpost.com/
Many other good projects and presentations (ones I wrote down): Control-f books.  Droplet. Electric go cart.  Improvs. Vote2eat. Trump tweets. Medbook.tech. Musically.me. Naptimes. Serial port game. Pass the paragraph. Refugestudent.com. Trump bot.  Rhythm fighter. Alg is simple. 3D gesture drawing.   Virtual Tetris.  

   
    
   

 

 

Okay.  The last photo is a joke. 

  

Assignment 6 (Dead Code Elimination)

This assignment is due Monday April 18th at 11:59pm.

For this assignment you are expected to identify and eliminate dead code. Dead code is any instruction that does not affect the output of the program (a function, in particular). For DCE (dead code elimination), you will need to use def-use chains to reason about instructions that do not affect the outputs. Remember that the output of a function is not limited to what it is returning.

IMPORTANT NOTE:

Those who implemented assignment 4 in LLVM, and have relied on the SSA property to find def-use chains with a linear scan of the LLVM-IR, are expected to implement a further requirement for this assignment, whether they are choosing URCC or LLVM for this assignment. That is Common Subexpression Elimination (CSE). An example of this optimization has been illustrated below.

CSE-example

Adopted from [1]

For CSE, you must first do the AVAIL analysis and then reason about expressions that are redundant.

Note 1: Since LLVM does not permit copy instructions, you may need to use the “ReplaceAllUsesWith” method to replace all uses of c with t. Also, since LLVM uses the SSA representation, you might need to insert new phi nodes.

Note 2: You do not need to implement partial redundancy elimination (PRE) for this assignment.

Testing

Your are expected to test your optimization pass by counting the number executed instructions. To do so, you are provided with a test script. Download this script into your URCC repository.

If you are using URCC for this assignment, you can easily run “./test.rb all” to run all the tests. You can also run an individual test by running “./test.rb #{program_name}”.

If you are using LLVM for this assignment, you will need to reimplement Test.test method in the script above by following the current implementation of that method. This is where you need to compile a program and apply your optimization, and instrumentation. You are allowed to use your peers’ test scripts.

The “./test.rb all” command will give you a “urcc_test_results.txt” file that includes the program outputs (along with your dynamic instruction count. Remember to print the instruction count as a single line “INST COUNT: x”, where x is the number of total executed instructions). Include this file in your report, along with your test script (if modified) and instructions on how to run the tests. Do not forget to give a thorough explanation about your implementation.

Note: URCC appears to be failing on generating a correct executable for two of the test cases: sort.c and tax.c. You can exclude these test cases by removing them from the test directory.

Assignment 5: Def-Use Chains

This assignment is due on Wednesday March 30th at 11:59pm.

In this assignment, you are expected to build the def-use chains for a program. You can either use your own CFG pass (if you are sure about its correctness), or adopt any correct CFG pass that is available to you.

Your output must have the following format. For every definition of a variable a, and for every use of a which is reachable from that definition (without any intervening def), you must output

[a, def, use],

where def and use are the program statements corresponding to the definition and use of a.

Run your analysis on the test cases provided in the URCC test directory and report the results. Explain your implementation and findings in a readme file. Archive everything and submit on blackboard.

Assignment 4: LVN in URCC/LLVM

For this assignment you are expected to implement the local value numbering optimization in URCC or LLVM. The requirements are the same as in assignment 1, except that the redundancy elimination part is now required. For this assignment, you don’t need to implement Stewart extension.

Test your optimization pass on URCC test cases. Report your implementation details and your findings in a readme file and submit on blackboard.

If you are working on LLVM, remember to turn off optimizations by using the “-O0” flag when emitting LLVM bitcode (The base project directory in /home/hoover/u1/cs255/cs255-llvm has been modified accordingly).

This assignment is due Sunday March 20th at 11:59pm.