The rapid evolution of computing demands curricula that reflect modern practices, yet many CS1 and CS2 courses continue to emphasize only sequential programming. This NSF-funded project addresses that gap by designing and disseminating exemplar CS1 and CS2 courses that integrate parallel, distributed, and event-driven computing as core concepts. The materials include unplugged activities and programming labs for both C++ and Java. To ensure broad applicability and adoption, development occurred in collaboration with instructors from six diverse institutions who are now implementing the materials. Evaluation includes surveys, assignment-specific instruments, and cross-team analysis. This poster presents the project’s vision, methods, and resources, highlighting how others can adopt and adapt them to teach modern computing.

Computer Science education, and all education for that matter, is being disrupted by Generative AI. While there have been few truly transformational technologies similar to AI, other incremental but impactful advances have helped shape the computing ecosystem. Other recent examples include the transition to multicore systems (requiring the promotion of parallel computing from an elective topic), the shift to graphical interfaces (raising expectations for assignments and motivating the creation of Media Computation), and the emergence of object-oriented programming. In this Birds of a Feather Session, we ask the question ''How might we redesign our CS1 and CS2 courses to better prepare students for emerging and future computing paradigms while maintaining strong foundations in problem solving, programming, and computational thinking?'' Using collaborative brainstorming techniques, participants will create a list of potential future paradigms (either disruptive or incremental) that are relevant to CS1/CS2, and develop proposed roadmaps that identify how those paradigms can be leveraged as contexts for teaching the existing CS1 and CS2 courses within the CS2023 curriculum.

Parallel and distributed computing (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 a 20th century model of algorithmic problem solving, where sequence, branch, and loop are the only organizing principles needed for algorithms. 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 a GPU in many cases. Most of their favorite applications use multiple cores and distributed resources. Often concurrency offers simpler solutions than sequential approaches. In this tutorial we overview key PDC concepts and provide examples of how they may naturally be incorporated in early computing classes. We lead participants through plugged and unplugged curriculum modules that have been successfully integrated and tested in existing computing classes at multiple institutions. We also discuss recent efforts at integrating AI methods, including LLMs, into early classes. In addition, we highlight other CDER activities for integration of PDC and AI into undergraduate computing curricula. Additional Information: No equipment or prior PDC experience is required, although a laptop that can run C++, Java and Python is recommended for following along with some code examples if desired.

Parallel and distributed computing (PDC) has become pervasive in all aspects of computing, so it is essential that students include parallelism and distribution in the computational thinking that they apply to problem solving, from the beginning of their computing education. With all computing devices that students use having multiple cores as well as a GPU in many cases, many students' favorite applications use multiple cores and/or distributed processors. However, we are still teaching them to solve problems using only sequential thinking. Why?

Parallel and distributed computing (PDC) has become pervasive in all aspects of computing, so it is essential that students include parallelism and distribution in the computational thinking that they apply to problem solving, from the very beginning of their computing education. With all computing devices that students use currently having multiple cores as well as a GPU in many cases, many students' favorite applications use multiple cores and/or distributed processors. However, we are still teaching them to solve problems using only sequential thinking. Why?

We consider the distributed setting of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the real plane. Robots may be without lights (the classic oblivious robots model) or equipped with lights (the robots with lights model). Under obstructed visibility, a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them, but it is not the case under unobstructed visibility. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. In this paper, we introduce and study Doorway Egress, the problem of robots exiting through a doorway from one side of a wall to the other; initially, the robots are positioned at distinct positions on one side of a wall.We study time-efficient solutions where time is measured using a standard notion of epochs – an epoch is a duration in which each robot completes at least one LCM cycle. For solutions to Doorway Egress with only 1 epoch, we: design an asynchronous algorithm if collisions are allowed; prove that an asynchronous algorithm is impossible if collisions are not allowed; and design a semi-synchronous algorithm without collisions. To further investigate asynchronous algorithms without collisions, we present algorithms with different combinations of robot abilities:•O(1) epochs with lights under obstructed visibility;•O(1) epochs without lights under unobstructed visibility; and•O(n) epochs without lights under obstructed visibility.Our results reveal dependencies and trade-offs among obstructed/unobstructed visibility, lights/no lights, and semi-synchronous/asynchronous settings.

Parallel and distributed computing (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 a 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. Industry is desperate for software engineers who think naturally in terms of exploiting these capabilities, rather than seeing them as an exotic upper-level topic that gets layered over a sequential solution. However, we are still teaching students to solve problems using sequential thinking. In this workshop we overview key PDC concepts and provide examples of how they may naturally be incorporated in early computing classes. We will introduce plugged and unplugged curriculum modules that have been successfully integrated in existing computing classes at multiple institutions. We will highlight the upcoming summer training workshop, for which we have funding to support attendance, as well as other CDER (Center for Parallel and Distributed Computing Curriculum Development and Educational Resources) activities.

This special session will report on the updated NSF/IEEE-TCPP Curriculum on Parallel and Distributed Computing released in Nov 2020 by the Center for Parallel and Distributed Computing Curriculum Development and Educational Resources (CDER). The purpose of the special session is to obtain SIGCSE community feedback on this curriculum in a highly interactive manner employing the hybrid modality and supported by a full-time CDER booth for the duration of SIGCSE. In this era of big data, cloud, and multi- and many-core systems, it is essential that the computer science (CS) and computer engineering (CE) graduates have basic skills in parallel and distributed computing (PDC). The topics are primarily organized into the areas of architecture, programming, and algorithms topics. A set of pervasive concepts that percolate across area boundaries are also identified. Version 1 of this curriculum was released in December 2012. That curriculum guideline has over 140 early adopter institutions worldwide and has been incorporated into the 2013 ACM/IEEE Computer Science curricula. This Version-II represents a major revision. The updates have focused on enhancing coverage related to the topical aspects of Big Data, Energy, and Distributed Computing.

We consider the distributed setting of$N$autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles following either the robots with lights model or the classical oblivious robots model. For the lights model, we assume obstructed visibility so that a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In contrast, we assume unobstructed visibility in the classical model so that a robot sees all others irrespective of their positions. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot's movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The Arbitrary Pattern Formationproblem is to relocate the$N$robots (starting at arbitrary but distinct initial positions on a grid) to form an arbitrary target pattern given as input. In this paper, we provide two asynchronous algorithms for Arbitrary Pattern Formation, one on the lights model and another on the classical model. Key measures of the algorithms' performance include the time taken and the number of moves by each robot. Both algorithms run in$O(\max\{D^{i}, D^{p}\})$time with$O(\max\{D^{i}, D^{p}\})$moves by each robot, where$D^{i}$and$D^{p}$, respectively, are the diameters of the initial and pattern configurations. The algorithm for the lights model uses$O(1)$colors. We also prove a lower bound of$\Omega(\max\{D^{i}, D^{p}\})$for time for any Arbitrary Pattern Formationalgorithm if scaling is not allowed on the target pattern. Therefore, our algorithms are optimal w.r.t. time. Furthermore, our algorithms are also optimal w.r.t. the number of moves given the existing lower bound of$\Omega(\max\{D^{i}, D^{p}\})$on the number of moves. In sum, our results show that having lights provides a trade-off on the unobstructed visibility requirement in the classical model for Arbitrary Pattern Formation.

We consider the distributed setting of$n$autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using a constant number of colored lights (therobots with lightsmodel). We assume obstructed visibility where collinear robots do not see each other. In addition, we consider a grid-based terrain embedded in the 2-dimensional euclidean plane. TheConvex Hull Formationproblem is to relocate the$n$robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this article, we provide a framework for solvingConvex Hull Formation. We then provide four asynchronous algorithms under this framework. Key measures of the algorithms’ performance include the time taken and the space occupied. The presented algorithms are randomized and their time bounds hold with high probability. The first$O(\max \lbrace n^{2},D\rbrace)$-time,$O({n^{2}})$-perimeter, and$O({n^{3}})$-area algorithm serves to introduce key ideas, where$D$is the diameter of the initial configuration. The subsequent algorithms, differing in computational requirements, run in$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)$time with a perimeter of$O(n^{\frac{3}{2}})$and area of$O(n^{3})$. We also prove lower bounds of$\Omega (n^{\frac{3}{2}})$for time and perimeter and$\Omega (n^{3})$for area, for anyConvex Hull Formationalgorithm; i.e., our$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)-$time algorithm is optimal in time, perimeter, and area.

We consider the distributed setting of n autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using a constant number of colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The CONVEX HULL FORMATION problem is to relocate the n robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this paper, we provide two asynchronous algorithms for CONVEX HULL FORMATION, both using a constant number of colors. Key measures of the algorithms' performance include the time taken and the space occupied (measured as the perimeter of the smallest rectangle enclosing the convex hull formed). The first O(max{n2, D})-time and O(n2)-perimeter algorithm serves to introduce key ideas, where D is the diameter of the initial 3 configuration. The second algorithm runs in O(max{n3/2, D}) 3 time with a perimeter of O(n3/2). We also prove lower bounds of Ω(n2/3) for both the time and perimeter for any CONVEX HULL FORMATION algorithm; that is, we establish our second algorithm as optimal in both time and perimeter.

Radio Frequency IDentification (RFID) systems are prevalent in all sorts of daily life endeavors. Most previous tag estimation schemes worked with relatively smaller frame size and large number of rounds. Here we propose a new estimator named \textquotedblleft Gaussian Estimator of RFID Tags,\textquotedblright (GERT), that works with large enough frame size to be accurately approximated to Gaussian distribution within a frame. The selection of the frame size is done according to Triangular Array Central Limit Theorem which also enables us to quantify the approximation error. Larger frame size helps the statistical average to converge faster to the ensemble mean of the estimator and the quantification of the approximation error helps to determine the number of rounds to keep up with the accuracy requirements. The overall performance of GERT is better than the previously proposed schemes considering the number of slots required for estimation to achieve a given level of estimation accuracy.

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using colored lights (the robots with lights model). We study the fundamental problem of repositioning N autonomous robots on a plane sothat each robot is visible to all others (the Complete Visibility problem) on this model; a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. There exists an O(1) time, O(1) color algorithm for this problem in the semi-synchronous setting. In this paper, we provide the first O(log N) time, O(1) color algorithm for this problem in the asynchronous setting. This is a significant improvement over an O(N)-time translation of the semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free - robots do not share positions and their paths do not cross.

No abstract available.

We consider the problem of repositioning N autonomous robots on a plane so that each robot is visible to all others (the Complete Visibility problem), a robot cannot see another robot if there is a third robot positioned between them on the straight line joining them. Robots communicate using collared lights. The computation is synchronous and each robot performs a look-compute-move during a round. Specifically, during a round a robot is permitted to observe the light and position of every robot visible to it. It may also perform an internal computation based on the observed lights and positions(including deciding on a new-collar for its own light), and possibly moving to a new position at the end of the round. The challenge posed by this model of computation stems from the fact that each robot has only a constant number of colours for its lights(symbols for communication) and no memory(except for the persistence of lights) between rounds. In this paper we first show that the best previously known algorithm for the complete visibility problem on this model runs in linear time in the worst case. We then present the first logarithmic time complexity algorithm for Complete Visibility. The model we assume use sterility, is fully-synchronous and allows robot paths to cross.

In this paper, we propose a novel model to study the efficiency of detecting latent connection relationships, represented by a given set of graphs, among N users. A subset of active nodes transmit following a common codebook over a multiple access Boolean channel. To maximize the error exponent of the structure detection, we formulate an optimization problem whose objective is to max-minimize the pairwise Chernoff information, and the constraint is a probability simplex due to the users' multiple dependency relationships, which are further shown to have close relationship to the internal connectivity of graphs. Case studies are provided to show certain inherent properties of the optimal solution. In addition, we present a particular case with two equally weighted complementary Paley graphs of prime square order, whose optimal solution for the codebook is proved and the resulting exponent is shown to be O(1/N). The case study demonstrates how the fundamental graph discrepancy property affects the solution to the problem.

In this paper, we propose a novel reservation system to study partition information and its transmission over a noise-free Boolean multiaccess channel. The objective of transmission is not to restore the message, but to partition active users into distinct groups so that they can, subsequently, transmit their messages without collision. We first calculate (by mutual information) the amount of information needed for the partitioning without channel effects, and then propose two different coding schemes to obtain achievable transmission rates over the channel. The first one is the brute force method, where the codebook design is based on centralized source coding; the second method uses random coding, where the codebook is generated randomly and optimal Bayesian decoding is employed to reconstruct the partition. Both methods shed light on the internal structure of the partition problem. A novel formulation is proposed for the random coding scheme, in which a sequence of channel operations and interactions induces a hypergraph. The formulation intuitively describes the transmitted information in terms of a strong coloring of this hypergraph. An extended Fibonacci structure is constructed for the simple, but nontrivial, case with two active users. A comparison between these methods and group testing is conducted to demonstrate the potential of our approaches.

In this paper, we consider the problem of partitioning active users in a manner that facilitates multi-access without collision. The setting is of a noisy, synchronous, Boolean, and multi-access channel, where K active users (out of a total of N users) seek channel access. A solution to the partition problem places each of the N users in one of K groups (or blocks), such that no two active nodes are in the same block. We consider a simple, but non-trivial and illustrative, case of K = 2 active users and study the number of steps T used to solve the partition problem. By random coding and a suboptimal decoding scheme, we show that for any T ≥ (C1+ ξ1) log N, where C1and ξ1are positive constants (independent of N), and where ξ1can be arbitrary small, the partition problem can be solved with error probability Pe(N)→ 0, for large N. Under the same scheme, we also bound T from the other direction, establishing that, for any T ≤ (C2- ξ2) log N, the error probability Pe(N)→ 1 for large N; again, C2and ξ2are constants, and ξ2can be arbitrarily small. These bounds on the number of steps are lower than the tight achievable lower bound in terms of T ≥ (Cg+ ξ) log N for group testing (in which all active users are identified, rather than just partitioned). Thus, partitioning may prove to be a more efficient approach for multi-access than group testing.

In this paper, we formulate a novel problem to quantify the amount of information transferred to partition active users who transmit following a common codebook over noisy Boolean multi-access channels. The objective of transmission is to ultimately let each active user aware of its own group only, not others. To solve the problem, we propose a novel framework by considering the decoding as a process of removing hyperedges of a complete hypergraph. For a particular, but non-trivial, case with two active users, an achievable bound for the defined partition information rate is found by using strong typical set decoding, as well as a large deviation technique for an induced Markov chain.

A decoder is a hardware module that expands an x-bit input into an n-bit output, where x << n. It can be viewed as producing a set S of subsets of an n-element set Zn. If this set S can be altered by the user, the decoder is said to be configurable. We propose a class of configurable decoders (called "mapping-unit" based decoders or simply MU-decoders) that facilitate efficient selection of elements in an FPGA (in general, in any chip). Conventional solutions for this selection use either (a) a fixed (non-reconfigurable) decoder that lacks the flexibility to generate many subsets quickly, or (b) a large look-up table (LUT) which is flexible, but too expensive. The proposed class of MU-decoders have much of the flexibility of the large-LUT solution (also called a LUT decoder here) at the cost of the fixed decoder solution. Specifically, we show that for any fixed gate cost, the a MU-decoder can produce any set of subsets that the LUT decoder can; in addition, the MU-decoder can exploit any available structure in the application at hand to produce many more subsets than the LUT decoder. We illustrate this ability in the context of totally ordered sets of subsets

Optics is acknowledged as the most viable means to meet the bandwidth needs of future interconnects. While the optical medium can easily deliver huge bandwidths, this bandwidth is difficult to harness; this is because of engineering and technological constraints associated with accommodating a large number of high-speed lasers and photodetectors within a small confine. We consider the problem of mapping weak multidimensional tori on optical slab waveguides. Our approach uses the fact that not all edges of a weak topology are used simultaneously; it uses this fact to employ a single laser/detector to work in multiple capacities at different times. We introduce the notion of aggregates to capture the cost of mapping a topology by our approach. We derive a non-trivial lower bound on this cost for a class of mappings and construct mappings, all of which surpass a naive method and some of which match the lower bound.

A multiple bus network (MBN) connects a set of processors via set of buses. Two important parameters of an MBN are its loading (largest number of connections on a bus) and its degree (largest number of connections to a processor). These parameters determine the cost, speed, and implementability of the MBN. The smallest degree that any useful MBN can have is 2. In this paper, we study the relationship between running time, degree, and loading of degree-2 MBNs running a fundamental class of algorithms called binary tree algorithms. (A binary tree algorithm reduces 2/sup n/ inputs at the leaves of a balanced-binary tree to a single result at the root of the tree.) Specifically, we establish a nontrivial /spl Omega/(n/logn) loading lower bound for any degree-2 MBN running a 2/sup n/ input binary tree algorithm optimally in n steps. We show that this bound does not hold if the restriction on the degree or the running time is relaxed. That is, optimal-time, degree-3, constant loading MBNs and suboptimal-time, degree-2, constant loading MBNs exist for binary tree algorithms. We also derive a lower bound on the additional time (beyond the optimal) needed to run binary tree algorithms on a degree-2, loading-L MBN, for any L>3.

This paper deals with the ability of a model to adapt algorithm instances of different sizes to run on a given model size without significant loss of efficiency. The overhead in simulating a step of a large instance of the model on a smaller instance can quantify this ability. A reconfigurable mesh (R-Mesh) can use its bus structure as a computational resource, presenting an obstacle to efficiently scaling down algorithms to run on a smaller R-Mesh. We construct a scaling simulation of a Fusing-Restricted Reconfigurable Mesh (FR-Mesh), a version of the R-Mesh. The overhead of this simulation depends only on the simulating machine size and not on the simulated machine size. Previously, the R-Mesh was not known to admit such a simulation overhead without significantly reducing its computational power. The small overhead holds importance for flexibility in algorithm design and for running algorithms with various input sizes on an available model of given size. The results of this paper extend to a variety of concurrent write rules and also translate to an improved scaling simulation of an unrestricted R-Mesh.

We consider a class of algorithms called fan-in algorithms, with numerous applications in problems involving semigroup operations. We present a multiple bus network (MBN) that runs any fan-in algorithm in optimal number of steps. The degree and loading of this MBN are each 3. We prove that the product of the degree and loading of any MBN that runs a fan-in algorithm in optimal time is at least 9. This establishes the proposed MBN to be optimal.

The distance transform is a basic operation in computer vision, pattern recognition and robotics. In this paper, we consider the city block (L1) distance metric. An algorithm for computing the city block distance transform on reconfigurable meshes is proposed in this paper. The time complexity and scalability of the algorithm are analysed. The results indicate that the algorithm is scalable and efficient.

We consider the problem of running ASCEND/DESCEND and FAN-IN algorithms on synchronous multiple bus networks with a restricted number of buses. Exact lower bounds on the time are derived. We present a method that runs FAN-IN algorithms optimally and ASCEND/DESCEND algorithms in one step beyond the lower bound.

The Reconfigurable Multiple Bus Machine (RMBM) is a model of parallel computation based on reconfigurable buses. In this paper, vie present constant time RMBM algorithms for a collection of basic, graph problems that include, lowest common ancestors and Euler tour related problems (for trees) and shortest path and connectivity related problems (for general graphs). We also present results for some poset and lattice problems. All algorithms are at least as efficient or more efficient in terms of processors than corresponding PARBUS algorithms.

A potential-driven approach to finding a rectilinear Steiner tree for a set of points on a planar grid is proposed. This approach has been implemented on a MasPar parallel processing system, and experimental results show its performance to be comparable with the best experimental results reported in the literature. Moreover, the method can be used for routing in grids with obstacles.>

We propose a class of new multiprocessor structures called bus based trees (BBTs) that are based on multiple buses. We show that a BBT can simulate a tree machine optimally. We also discuss optimal VLSI layouts for the BBT and show that the BBT can be used as a building block to construct new powerful parallel computing structures.

The Reconfigurable Multiple Bus Machine (RMBM) is a model of parallel computation based on reconfigurable buses. We present constant time algorithms for list ranking, integer sorting and a number of fundamental graph problems on the RMBM. The algorithms are more efficient in terms of processors than the corresponding PARBS algorithms. The algorithms demonstrate some of the potential for computation available in the ability to manipulate communication paths as a vital part of computation.