IV Performance

GPU Based Methods

Instance	CUDA-Cut	CUDA-Cut	Fast-Cut	JF-Cut	Speedup	Speedup
Name	Accuracy	Time(ms)	Time(ms)	Time(ms)	-/CUDA	-/Fast
flower	0.736	48.6	9.7	4.2	11.5	2.3
4 x 4	0.673	622.2	262.4	90.0	6.9	2.9
16 x 16	-	-	9636.7	2192.3	-	4.4
person	0.358	73.9	20.9	10.0	7.4	2.1
4 x 4	0.674	612.0	290.9	120.7	5.1	2.4
16 x 16	-	-	12131.0	3403.6	-	3.6
sponge	1.000	48.7	5.4	4.4	11.0	1.2
4 x 4	0.973	637.3	151.7	31.4	20.3	4.8
16 x 16	-	-	3689.5	595.3	-	6.2
bone	-	-	5643.6	616.9	-	9.1
2 x 2 x 2	-	-	68712.3	6749.9	-	10.2
liver	-	-	6211.4	585.7	-	10.6
2 x 2 x 2	-	-	165704.3	16441.2	-	10.1
babyface	-	-	7932.5	830.2	-	9.6
2 x 2 x 2	-	-	104277.6	11309.2	-	9.2
adhead	-	-	17084.4	1654.6	-	10.3
2 x 2 x 2	-	-	115991.0	10511.7	-	11.0
madagascar	-	-	49559.9	24465.4	-	2.0
lta	-	-	95605.9	51279.0	-	1.9
timescapes	-	-	357.2	78.6	-	4.5
the croods	-	-	9410.7	1374.6	-	6.8
life of pi	-	-	743.4	80.9	-	9.2
mrbrain	-	-	9381.0	1226.2	-	7.7
lobster	-	-	2892.9	321.5	-	9.0

Convergence Speed

Instance	Iterations	Iterations	Iterations	Ratios	Ratios
Name	CUDA	Fast-Cut	JF-Cut	-/CUDA	-/Fast
flower	155	41	10	15.5	4.1
4 x 4	232	174	81	2.9	2.1
16 x 16	-	516	195	-	2.6
person	232	100	26	8.9	3.8
4 x 4	232	203	88	2.6	2.3
16 x 16	-	692	366	-	1.9
sponge	155	31	14	11.1	2.2
4 x 4	232	114	27	8.6	4.2
16 x 16	-	234	84	-	2.8
bone	-	265	125	-	2.1
2 x 2 x 2	-	410	184	-	2.2
liver	-	498	170	-	2.9
2 x 2 x 2	-	1721	697	-	2.5
babyface	-	512	194	-	2.6
2 x 2 x 2	-	876	413	-	2.1
adhead	-	518	197	-	2.6
2 x 2 x 2	-	439	175	-	2.5
madagascar	-	1344	609	-	2.2
lta	-	1344	668	-	2.0
timescapes	-	36	13	-	2.8
the croods	-	68	34	-	2.0
life of pi	-	32	10	-	3.2
mrbrain	-	516	282	-	1.8
lobster	-	214	104	-	2.1

CPU Based Methods

Instance	BK	Grid-Cut	Grid-Cut	JF-Cut	JF-Cut	JF-Cut	JF-Cut
Name	Total	1 Thread	8 Threads	Total	-/BK	-/GC-1	-/GC-8
flower	29	18	6	6	4.7	2.9	1.0
4 x 4	495	131	89	101	4.9	1.3	0.9
16 x 16	9850	2392	1462	1575	6.3	1.5	0.9
person	29	9	7	14	2.1	0.6	0.5
4 x 4	494	121	92	118	4.2	1.0	0.8
16 x 16	9111	2069	1377	2417	3.8	0.9	0.6
sponge	28	7	6	13	2.2	0.6	0.5
4 x 4	466	93	79	41	11.5	2.3	1.9
16 x 16	7537	1531	1265	595	12.7	2.6	2.1
bone	5761	867	519	421	13.7	2.1	1.2
2 x 2 x 2	204874	32057	20402	4707	43.5	6.8	4.3
liver	10769	3254	3916	305	35.3	10.7	12.8
2 x 2 x 2	855279	237593	256249	7923	107.9	30.0	32.3
babyface	8940	2619	1501	459	19.5	5.7	3.3
2 x 2 x 2	809026	231592	233656	5825	138.9	39.8	40.1
adhead	23192	6517	4149	980	23.7	6.6	4.2
2 x 2 x 2	223934	41414	21274	7921	28.3	5.2	2.7
madagascar	114673	29658	12269	13730	8.4	2.2	0.9
lta	104006	32055	13139	24275	4.3	1.3	0.5
timescapes	18175	3640	2741	-	-	-	-
the croods	12603	2883	2115	906	13.9	3.2	2.3
life of pi	11700	3925	2162	209	55.9	18.8	10.3
mrbrain	3902	599	597	798	4.9	0.8	0.7
lobster	7028	1428	657	229	30.7	6.2	2.9

Complexity Analysis

Metric	Dimension	Block Size	Wave Push	Wave Push	Block-Wise

• | - | - | CUDA | Fast-Cut | JF-Cut N | 2 | - | 0.25 | 0.25 | 4 N | 3 | - | - | 0.13 | 6 D | 2 | 16×16 | 16 | 16 | 256 D | 2 | 32×32 | 32 | 32 | 1024 D | 3 | 4×4×4 | - | 4 | 64 D | 3 | 8×8×8 | - | 8 | 512