Parallel and distributedcomputing (PDC) has become pervasive in all aspects of computing, and thus it is essential that students include parallelism and distribution in the computational thinking that they apply to p...
详细信息
ISBN:
(纸本)9781450390712
Parallel and distributedcomputing (PDC) has become pervasive in all aspects of computing, and thus it is essential that students include parallelism and distribution in the computational thinking that they apply to problem solving, from the very beginning. Computer science education is still teaching to a 20th century model of algorithmic problem solving. Sequence, branch, and loop are taught in our early courses as the only organizing principles needed for algorithms, and we invest considerable time in showing how best to sequentially process large volumes of data. All computing devices that students use currently have multiple cores as well as GPU in many cases. Most of their favorite applications use multiple cores and numbers of distributed processors. Often concurrency offers simpler solutions than sequential approaches. acm and ABET have recommended including PDC in the undergraduate CS curriculum. However, we are still teaching them to solve problems using sequential thinking. In this workshop we overview the key PDC concepts and provide examples of how they may naturally be incorporated in early CS classes. We will introduce plugged and unplugged curriculum modules that have been successfully integrated in existing CS classes at multiple institutions. We will highlight the upcoming summer training that we are organizing, for which we have funding to support attendance.
This work studies a distributed cooperation problem under an extreme assumption that no two processors may be able to communicate during a prolonged period of time. For problems where the quality of distributed decisi...
ISBN:
(纸本)9781581131833
This work studies a distributed cooperation problem under an extreme assumption that no two processors may be able to communicate during a prolonged period of time. For problems where the quality of distributed decision-making depends on, and can be traded for, communication, the solution space needs to consider the possibility of no communication. Notably, this is the case in the load-balancing setting introduced by Papadimitriou and Yanakakis [PY] and studied by Georgiades, Mavronicolas and Spirakis [GMS]. The distributed cooperation problem that we consider here is defined for n processors in terms of t tasks that need to be performed efficiently and that are known to all processors. The fact that the tasks are initially known makes it possible for the problem to be solved in the absence of communication. The efficiency requirement and the possibility of eventual availability of communication make it desirable to structure the work of the processors so that when eventually some processors are able to communicate, the amount of wasted (redundant) work they have collectively performed prior to that time is controlled. We model solutions to the problem as sets of n lists of distinct tasks from {1,…,t}. We call such lists schedules. We define and study the notion of k-waste that, for a set of n schedules, measures the maximum number of redundant task identifiers contained in any subset of k (≤ n) schedules. We are interested in expressing k-waste as a function of the length of schedules. Our goal is to construct n schedules of length t such that k-waste is controlled for any prefixes of the *** et al. [DSS] developed a solution to this problem where each processor performs up to Θ(3√n) tasks and at most one redundant task is performed for any pair of processors (i.e., 2-waste is equal to 1). In our work we establish a lower bound for the class of schedules considered in [DSS]. Assuming the most challenging case n = t, we show that for schedules longer tha
暂无评论