Memory Access Coloring provides architecture support that allows software to classify memory accesses into different congruence classes by specifying a color for each memory access operation. The color information is received and recorded by the underlying system with appropriate granularity. This allows hardware to monitor color-based cache monitoring information and provide such feedback to the software to enable various runtime optimizations. It also enables enforcement of different memory consistency models for memory regions with different colors at the same time.