Image segmentation is a key area of research in computer vision. Recent advances facilitated reformulation of the non-convex multi-phase segmentation problem as a convex optimization problem (see for example [2, 4, 9, 10, 13, 16]). Recently, [3] proposed a new convex relaxation approach for a class of vector-valued minimization problems, and this approach is directly applicable to the widely used classical Mumford-Shah segmentation model [11]. While the approach in [3] provides the much deserved convexification, it achieves this at the expense of an increased computational complexity due to the increased dimensionality of the reformulated problem; however, the algorithm proposed in [3] can indeed profit from a parallelized implementation. In this paper, we present a GPU-based implementation of the convex formulation for Mumford-Shah piecewise constant multi-phase image segmentation algorithm proposed in [3]. The main goal of this paper is to provide insights into the way the algorithm has been parallelized in order to obtain good speedup. We present multi-phase segmentation results both on synthetic and real images. The speedup of GPU based implementation is evaluated on three different GPUs. For sufficiently large images, the speedup achieved on GTX 285 GPU is around 40, compared to an optimized CPU implementation. The speedups obtained from GPU-based implementation are quite satisfactory. We also made our CUDA code available online.