The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently due to the popularity of computations as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we deriveSPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present howSPINsolves it with a rounding-based randomized approximation approach. Our analysis indicatesSPINachieves a good performance guarantee efficiently. Moreover,SPINis robust against misestimation of job execution time by theoretically bounding its negative impact. We implementSPINon a production-trace driven testbed with 40 GPUs. Our extensive experiments show thatSPINcan reduce the job makespan and the average job completion time by up to$3\times $and$4.68\times $, respectively.SPINalso demonstrates better robustness to execution time misestimation compared with state-of-the-art heuristic baselines.

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently because of the pop-ularity of computations such as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we derive SPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present how SPIN solves it with a rounding-based randomized approximation approach. Our analysis indicates SPIN achieves a good performance guarantee efficiently. Moreover, SPIN is robust against misestimation of job execution time by theoretically bounding its negative impact. We implement SPIN on a production-trace driven testbed with 40 GPUs. Our extensive experiments show that SPIN can reduce the job makespan and the average job completion time by up to 3× and 4.68×, respectively. Our approach also demonstrates better robustness to execution time misestimation compared with heuristic baselines.

In this paper, we study online deadline-aware task dispatching and scheduling in edge computing. We jointly consider management of the networking bandwidth and computing resources to meet the maximum number of deadlines. We propose an online algorithm Dedas, which greedily schedules newly arriving tasks and considers whether to replace some existing tasks in order to make the new deadlines satisfied. We derive a non-trivial competitive ratio theoretically, and our analysis is asymptotically tight. We then build DeEdge, an edge computing testbed installed with typical latency-sensitive applications such as IoT sensor monitoring and face matching. Besides, we adopt a real-world data trace from the Google cluster for large-scale emulations. Extensive testbed experiments and simulations demonstrate that the deadline miss ratio of Dedas is stable for online tasks, which is reduced by up to 60% compared with state-of-the-art methods. Moreover, Dedas performs well in minimizing the average task completion time.

Segmentation of pheochromocytomas in contrast-enhanced computed tomography (CECT) images is an ill-posed problem due to the presence of weak boundaries, intratumoral degeneration, and nearby structures and clutter. Additional information from different phases of CECT images needs to be imposed for better mass segmentations. In this paper, a novel adaptive cosegmentation method is proposed by incorporating a localized region-based level set model (LRLSM). The energy function is formulated with consideration of adaptive tradeoff between the complementary local information from image pairs. Gradient direction and shape dissimilarity measure are integrated to guide the level set evolution. Automatic localization radius selection is added to further facilitate the segmentation. Then, two level set functions from each image pair are evolved and refined alternately to minimize the energy function. Experimental results in 50 CECT image pairs show that the adaptive LRLSM-based method is effective in segmentation of pheochromocytoma at two phases and produces better results, especially in the cases with weak boundaries, and complex foreground and background.