More Complex Cache Hierarchies

Figure 14: A tree-like multi-path cache hierarchy. Traces do not overlap (2 million reads each). For ease of comparison between caches, the individual hit ratio contributions are normalized based on the total number of reads in the cache hierarchy.

		Hit Ratio Contribution				Traf. (MBlocks)		Avg.
		= hits / 4000000				C1a-	C1b-	Resp.
		C1a	C1b	C2	Aggr	C2	C2	Time
	DEMOTE-LRU	0.14	0.10	0.12	0.36	2.83	3.16	3.45
	PROMOTE-LRU	0.14	0.12	0.10	0.36	1.46	1.54	3.45
P1+P2	PROMOTE-ARC	0.16	0.14	0.13	0.43	1.36	1.43	3.13
	OPT-LB	0.27	0.24	0.10	0.61	0.90	1.04	2.29
	OPT-UB	0.27	0.24	0.12	0.63	0.90	1.04	2.12
	DEMOTE-LRU	0.02	0.10	0.10	0.23	3.77	3.16	4.01
	PROMOTE-LRU	0.04	0.11	0.08	0.23	1.83	1.55	4.01
P1+P3	PROMOTE-ARC	0.10	0.14	0.10	0.34	1.59	1.45	3.51
	OPT-LB	0.20	0.24	0.12	0.56	1.21	1.04	2.53
	OPT-UB	0.20	0.24	0.14	0.59	1.21	1.04	2.29
	DEMOTE-LRU	0.02	0.10	0.06	0.18	3.82	3.16	4.23
	PROMOTE-LRU	0.01	0.11	0.06	0.18	1.94	1.55	4.22
P1+P4	PROMOTE-ARC	0.03	0.14	0.10	0.27	1.87	1.45	3.85
	OPT-LB	0.09	0.24	0.08	0.41	1.66	1.04	3.20
	OPT-UB	0.09	0.24	0.11	0.44	1.66	1.04	2.98
	DEMOTE-LRU	0.03	0.10	0.08	0.21	3.68	3.16	4.08
	PROMOTE-LRU	0.04	0.13	0.05	0.22	1.86	1.55	4.06
P1+P5	PROMOTE-ARC	0.09	0.14	0.09	0.32	1.66	1.43	3.60
	OPT-LB	0.17	0.24	0.10	0.51	1.33	1.04	2.74
	OPT-UB	0.17	0.24	0.12	0.53	1.33	1.04	2.53

Figure 15: An inverted tree-like single-path cache hierarchy. Two traces are merged before presenting to cache $C_1$. For ease of comparison between caches, the individual hit ratio contributions are normalized based on the total number of reads in the cache hierarchy.

		Hit Ratio Contribution				Traf. (MBlocks)		Avg.
		= hits / 4000000				C1-	C1-	Resp.
		C1	C2a	C2b	Aggr	C2a	C2b	Time
	DEMOTE-LRU	0.19	0.10	0.06	0.35	3.17	3.27	3.50
	PROMOTE-LRU	0.18	0.11	0.06	0.35	1.73	1.54	3.49
P1+P2	PROMOTE-ARC	0.23	0.13	0.07	0.43	1.62	1.46	3.18
	OPT-LB	0.46	0.06	0.08	0.60	1.05	1.09	2.35
	OPT-UB	0.46	0.00	0.00	0.63	1.05	1.09	2.10
	DEMOTE-LRU	0.11	0.08	0.07	0.25	3.83	3.25	3.93
	PROMOTE-LRU	0.15	0.04	0.05	0.24	1.87	1.55	3.97
P1+P3	PROMOTE-ARC	0.20	0.08	0.06	0.35	1.78	1.40	3.52
	OPT-LB	0.40	0.06	0.10	0.56	1.33	1.08	2.57
	OPT-UB	0.40	0.00	0.00	0.59	1.33	1.08	2.27
	DEMOTE-LRU	0.13	0.01	0.06	0.20	3.87	3.04	4.15
	PROMOTE-LRU	0.11	0.02	0.06	0.19	1.96	1.58	4.20
P1+P4	PROMOTE-ARC	0.17	0.03	0.06	0.26	1.96	1.37	3.88
	OPT-LB	0.32	0.05	0.03	0.41	1.75	0.95	3.21
	OPT-UB	0.32	0.00	0.00	0.44	1.75	0.95	2.98
	DEMOTE-LRU	0.12	0.04	0.07	0.22	3.75	3.27	4.07
	PROMOTE-LRU	0.13	0.03	0.06	0.22	1.91	1.58	4.07
P1+P5	PROMOTE-ARC	0.18	0.07	0.07	0.31	1.86	1.44	3.66
	OPT-LB	0.36	0.06	0.09	0.51	1.49	1.06	2.77
	OPT-UB	0.36	0.00	0.00	0.53	1.49	1.06	2.51

PROMOTE can be applied to complex hierarchies. As the possible configurations are endless, we pick two simple and yet interesting configurations for our experiments.