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?

A segment tree is a versatile tree-based data structure over intervals or line segments efficiently supporting several computational operations such as stabbing query, segment arrangement, and planar point location, both theoretically and practically. Polygon clipping is a basic operation in domains such as Computer Graphics, Computer-aided Design, and Geographic Information Science (GIS). Given two polygons with n vertices, polygon clipping algorithms find the geometric intersection or union in <?TeX $\mathcal {O}(n^2)$?> Math 1 time using Foster’s all-to-all edge intersection testing and <?TeX $\mathcal {O}((n+k)\log n)$?> Math 2 time using Vatti’s sweep line-based method, where k is the number of intersections. No known segment tree implementation, including the CGAL library, supports intersection finding or polygon clipping. We extended the segment tree leveraging Chaselle’s PRAM-model augmentation, parallelized the construction of our augmented segment tree, and employed it to find line segment intersections for polygon clipping while handling degenerate cases. Augmented segment tree eliminates 99% of non-intersecting edge pairs compared to 63% by the state-of-the-art filtering based on common minimum bounding rectangle method employed in Foster’s GPU-based implementation. This, coupled with Ω(nlog n) work on a single CPU core, beats Foster’s GPU performance with <?TeX $\mathcal {O}(n^2)$?> Math 3 work. Our OpenMP directive based multi-core implementation achieves up to 4X relative speedup for clipping two polygons with 182K vertices and 5X speedup for five polygons with 398K vertices. We also offloaded the parallel kernels to a GPU using OpenACC achieving performance competitive with Foster’s GPU implementation. Our profiling indicates limitations of the compiler directives and potential for superior performance by employing pthread/cuda libraries.

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?

Polygonal geometric operations are fundamental in domains such as Computer Graphics, Computer-Aided Design, and Geographic Information Systems. Handling degenerate cases in such operations is important when real-world spatial data are used. The popular Greiner-Hormann (GH) clipping algorithm does not handle such cases properly without perturbing vertices leading to inaccuracies and ambiguities. In this work, we parallelize the$O$(n2)-time general polygon clipping algorithm by Foster et al., which can handle degenerate cases without perturbation. Our CREW PRAM algorithm can perform clipping in O (log n) time using$n$+$k$number of processors with simple polygons, where$n$is the number of input edges and$k$is the number of edge intersections. For efficient GPU implementation, we employ three effective filters which have not been used in prior work on polygon clipping: 1) Common-minimum-bounding-rectangle filter, 2) Count-based filter, and 3) Line-segment-minimum-bounding-rectangle filter. They drastically reduce O($n$2) candidate edge pairs comparisons by 80% - 99%, leading to significantly faster parallel execution. In our experiments, C++ CUDA-based implementation yields up to 40X speedup over real-world datasets, processing two polygons with a total of 174K vertices on an Nvidia Quadro RTX 5000 GPU compared to the sequential Foster's algorithm running on an Intel Xeon Silver 4210R CPU.

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.

Decision trees and tree ensembles are popular supervised learning models on tabular data. Two recent research trends on tree models stand out: (1) bigger and deeper models with many trees, and (2) scalable distributed training frameworks. However, existing implementations on distributed systems are IO-bound leaving CPU cores underutilized. They also only find best node-splitting conditions approximately due to row-based data partitioning scheme. In this paper, we target the exact training of tree models by effectively utilizing the available CPU cores. The resulting system called TreeServer adopts a column-based data partitioning scheme to minimize communication, and a node-centric task-based engine to fully explore the CPU parallelism. Experiments show that TreeServer is up to 10× faster than models in Spark MLlib. We also showcase TreeServer's high training throughput by using it to build big “deep forest” models.

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 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.

Colocation patterns refer to subsets of spatial features whose instances are frequently located together. Mining colocation patterns is important in many applications such as identifying relationships between diseases and environmental factors, but is computationally challenging due to the large number of instances and candidate patterns. Existing algorithms are mostly sequential, and thus can be insufficient for big spatial event data. Recently, parallel colocation mining algorithms have been developed based on the Map-reduce framework, which is economically expensive. Another work proposed a GPU algorithm based on iCPI tree, but assumes that the number of neighbors for each instance is within a small constant, and thus cannot be used when instances are dense and unevenly distributed. To address these limitations, we recently proposed grid-based GPU colocation mining algorithms that include a novel cell-aggregate-based upper bound filter, and two refinement algorithms. In this paper, we provide theoretical analysis of running time. Furthermore using GPU profiling, we identify our recent GPU implementation, GPU-grid-join, as a memory bound problem and to address its bottlenecks, we proposes GPU-grid-join+, an optimized GPU algorithm. Our experimental results on real world data shows that GPU-grid-join+ achieves 4 to 12-fold speedup over GPU-grid-join both running on Nvidia P100 GPU as well as 56 to 126-fold speedup over OpenMP implementation over Intel(R) Xeon(R) CPU with 12 cores. Also for synthetic data, the speedup is in ranges 3 to 7-fold and 9 to 42-fold respectively.

Parallel and distributed computing (PDC) is now a pervasive aspect of deployed systems, 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. Our students all have multicore laptops. Most of their favorite applications use vast numbers of distributed processors. Why are we still teaching them to solve problems using only sequential thinking? Come to this workshop to see how easy it is to open their eyes to exploiting concurrency in problem solving, starting in their earliest courses. You'll hear about and experience some unplugged activities, learn how to help students recognize examples of concurrency in the world around them, see how event driven user interfaces can easily exemplify issues related to multithreading, and how freely available libraries can be used to naturally exploit parallelism in working with large data structures. We will also highlight the two summer training programs that we are organizing, for which we have funding to support attendance by instructors. Having a laptop that can run Java and C++ will allow you to follow along with some code examples, but isn't necessary.

In recent times, geospatial datasets are growing in terms of size, complexity and heterogeneity. High performance systems are needed to analyze such data to produce actionable insights in an efficient manner. For polygonal a.k.a vector datasets, operations such as I/O, data partitioning, communication, and load balancing becomes challenging in a cluster environment. In this work, we present MPI-Vector-IO 1, a parallel I/O library that we have designed using MPI-IO specifically for partitioning and reading irregular vector data formats such as Well Known Text. It makes MPI aware of spatial data, spatial primitives and provides support for spatial data types embedded within collective computation and communication using MPI message-passing library. These abstractions along with parallel I/O support are useful for parallel Geographic Information System (GIS) application development on HPC platforms.

No abstract available.

Grid-based techniques are well-suited for spatial join algorithms over General Purpose Graphic Processing Unit (GPGPU) architectures because of their non-hierarchical structure. However, these techniques are well-established years before the existence of GPU computing. As a result, they do not fully take advantage of many-core architectures. Last year, we had introduced a spatial join GPU system based on discarding even those cross-layer pairs of polygons whose Minimum Bounding Rectangles (MBRs) intersect but their rectangular intersection does not contain edges from both layers. These MBR intersections are called Common MBRs. In this extended abstract, we briefly introduce CMF-Grid: a non-uniform GPU-based grid technique over such Common MBRs, that can be used in polygonal spatial join operations such as overlay, edge-intersection etc. to significantly reduce their computationally-extensive refinement phase workload. Based on our experimental results on real datasets, CMF-Grid can cut down the refinement phase workload by more than 30, 000 times that of all-to-all algorithms and it improves upon its predecessor, CMF filter, by 700 times. Our upgraded spatial join system with ST_intersect predicate is able to process more than 600, 000 polygons with more than 2 billions edges on a single GPU in less than a second end-to-end processing time that is 225% time improvement compared to GCMF, the state of the art GPU-based system. The system also achieves up to 200-fold end-to-end speedup versus the best optimized sequential routines of GEOS C++ library as well as PostgreSQL spatial database with PostGIS.

Frequent subgraph pattern mining (FSM) finds subgraph patterns that occur in a graph database with a frequency that is more than a given threshold. In FSM, the notion of occurrence captures the presence or absence of a node and an edge in a binary fashion and considers relevance of each edge or node as same. However, an edge or a node may have different relevancy score. Therefore, the utility of a pattern should be defined using the relevance score of participating edges or nodes. This paper defines the utility notion of a pattern using this idea and presents algorithms to mine high-utility patterns from a given graph database. A significant issue in high-utility pattern mining is that the antimonotonic property no longer holds contrary to the FSM. Hence pruning of the search space becomes a daunting task. To address this issue, we incorporate a function to estimate an upper-bound utility of a pattern object that also satisfies the anti-monotonic property. This paper presents three optimization heuristics for the solution on a distributed platform, namely, a novel use of bloom filter to avoid exploration of non-candidates, avoidance of sending database information with each pattern, and avoidance of sending pattern embeddings with each pattern. The experimental study on Apache Spark shows the effectiveness of our proposed optimization strategies.

Given two layers of large polygonal datasets, detecting those pairs of cross-layer polygons which satisfy a join predicate, such as intersection or contain, is one of the most computationally intensive primitive operations in the spatial domain applications. In this work, we introduce GCMF, an end-to-end software system, that is able to handle spatial join (with ST_Intersect operation) over non-indexed polygonal datasets with over 3 GB file size comprising more than 600, 000 polygons on a single GPU within less than 8 sec by applying innovative filter and refinement techniques. GCMF performs a two-step filtering phase. 1) A sort-based Minimum Bounding Rectangle (MBR) filtering step detects potentially overlapping polygon pairs up to 20 times faster than the optimized GEOS library routine. 2) A linear time Common MBR filtering step (based on the overlapping area of two given MBRs) that not only eliminates two-third of the candidate polygon pairs but also reduces the number of edges to be considered in the refinement phase by 40-fold on an average based on our experimental results with real datasets. Furthermore, for the refinement phase, GCMF implements a load-balanced parallel point-in-polygon and edge-intersection tests over GPU. Our experimental results with three different real datasets show up to 39-fold end-to- end speedup versus optimized sequential routines of GEOS C++ library as well as PostgreSQL spatial database with PostGIS.

Clipping arbitrary polygons is one of the complex operations in computer graphics and computational geometry. It is applied in many fields such as Geographic Information Systems (GIS) and VLSI CAD. We have two significant results to report. Our first result is the effective parallelization of the classic, highly sequential Greiner-Hormann algorithm, which yields the first output-sensitive CREW PRAM algorithm for a pair of simple polygons, and can perform clipping in O(logn) time using O(n+k) processors, where n is the total number of vertices and k is the number of edge intersections. This improves upon our previous clipping algorithm based on the parallelization of Vatti's sweepline algorithm, which requires O(n+k+k') processors to achieve logarithmic time complexity where k' can be O(n2). This also improves upon another O(logn) time algorithm by Karinthi, Srinivas, and Almasi which unlike our algorithm does not handle self-intersecting polygons, is not output-sensitive, and must employ O(n2) processors to achieve O(logn) time. We also study multi-core and many-core implementations of our parallel Greiner-Hormann algorithm. Our second result is a practical, parallel GIS system, namely MPI-GIS, for polygon overlay processing of two GIS layers containing large number of polygons over a cluster of compute nodes. It employs R-tree for efficient indexing and identification of potentially intersecting set of polygons across two input GIS layers. Spatial data files tend to be large in size (in GBs) and the underlying overlay computation is highly irregular and compute intensive. This system achieves 44X speedup on a 32-node NERSC's CARVER cluster while processing about 600K polygons in two GIS layers within 19 seconds which takes over 13 minutes on state-of-art ArcGIS system.

Message Passing Interface (MPI) has been the predominant standardized system for writing parallel and distributed applications. However, while MPI has been the software system of choice for traditional parallel and distributed computing platforms such as large compute clusters and Grid, MPI is not the system of choice for cloud platforms. The primary reasons for this is the lack of low latency high bandwidth network capabilities of the cloud platforms and the inherent architectural differences from traditional compute clusters. Prior studies suggest that the message latency of cloud platforms could be as much as 35x slower than that of an infiniband-connected cluster [1] for popular MPI implementations. MPI-like environment on cloud platforms is desirable for a large class of applications that run for long time spans with varying computing needs, such as the modeling and analysis to predict swath of a hurricane. Such applications could benefit from cloud's resiliency and on-demand access for a robust and green solution. Interestingly, most of the cloud vendors provide APIs to access cloud resources in an efficient manner different than how an MPI implementation would avail of those resources. We have done extensive research to identify the pain-points for designing and implementing an MPI-like framework for cloud platforms. Our research has provided us with vital guidelines that we are sharing in this paper. We present the details of the key components required for such a framework along with our experience while implementing a preliminary MPI-like framework over Azure dubbed cloud MPI and evaluate its pros and cons. A large GIS application has been ported over cloud MPI to study its effectiveness and limitations.

Polygon clipping is one of the complex operations in computational geometry. It is a primitive operation in many fields such as Geographic Information Systems (GIS), Computer Graphics and VLSI CAD. Sequential algorithms for this problem are in abundance in literature but there are very few parallel algorithms solving it in its most general form. We present the first output-sensitive CREW PRAM algorithm, which can perform polygon clipping in O(logn) time using (n + k + k') processors, where n is the number of vertices, k is the number of edge intersections and k' is the additional temporary vertices introduced due to the partitioning of polygons. The current best algorithm by Karinthi, Srinivas, and Almasi [1] does not handle self-intersecting polygons, is not output-sensitive and must employ ⊝(n2) processors to achieve O(logn) time. Our algorithm is developed from the first principles and it is superior to [1] in cost. It yields a practical implementation on multicores and demonstrates 30x speedup for real-world dataset. Our algorithm can perform the typical clipping operations including intersection, union, and difference.

Parallelism pervades all aspects of modern computing, from in-home devices such as cell phones to large-scale supercomputers. Recognizing this - and motivated by the premise that every undergraduate student in a computer-related field should be prepared to cope with parallel computing - a working group sponsored by NSF and IEEE/TCPP, and interacting with the ACM CS2013 initiative, has developed guidelines for assimilating parallel and distributed computing (PDC) into the core undergraduate curriculum. Over 100 Early-Adopter institutions worldwide are currently modifying their computer-related curricula in response to the guidelines. Additionally, the CDER Center for Curriculum Development and Educational Resources, which grew out of the working group, is currently assembling a book of contributed essays on how to teach PDC topics in lower-level CS/CE courses, to fill the serious lack of textual material for students and instructors.

Spatial overlay processing is a widely used compute-intensive GIS application that involves aggregation of two or more layers of maps to facilitate intelligent querying on the collocated output data. When large GIS data sets are represented in polygonal (vector) form, spatial analysis runs for extended periods of time, which is undesirable for time-sensitive applications such as emergency response. We have, for the first time, created an open-architecture-based system named Crayons for Azure cloud platform using state-of-the-art techniques. During the course of development of Crayons system, we faced numerous challenges and gained invaluable insights into Azure cloud platform, which are presented in detail in this paper. The challenges range from limitations of cloud storage and computational services to the choices of tools and technologies used for high performance computing (HPC) application design. We report our findings to provide concrete guidelines to an eScience developer for 1) choice of persistent data storage mechanism, 2) data structure representation, 3) communication and synchronization among nodes, 4) building robust failsafe applications, and 5) optimal cost-effective utilization of resources. Our insights into each challenge faced, the solution to overcome it, and the discussion on the lessons learnt from each challenge can be of help to eScience developers starting application development on Azure and possibly other cloud platforms.

An efficient parallel priority queue is at the core of the effort in parallelizing important non-numeric irregular computations such as discrete event simulation scheduling and branch-and-bound algorithms. GPGPUs can provide powerful computing platform for such non-numeric computations if an efficient parallel priority queue implementation is available. In this paper, aiming at fine-grained applications, we develop an efficient parallel heap system employing CUDA. To our knowledge, this is the first parallel priority queue implementation on many-core architectures, thus represents a breakthrough. By allowing wide heap nodes to enable thousands of simultaneous deletions of highest priority items and insertions of new items, and taking full advantage of CUDA's data parallel SIMT architecture, we demonstrate up to 30-fold absolute speedup for relatively fine-grained compute loads compared to optimized sequential priority queue implementation on fast multicores. Compared to this, our optimized multicore parallelization of parallel heap yields only 2-3 fold speedup for such fine-grained loads. This parallelization of a tree-based data structure on GPGPUs provides a roadmap for future parallelizations of other such data structures.

Efficient searching for information is an important goal in unstructured peer-to-peer (P2P) networks. While several P2P systems have been proposed for data sharing purposes, many support only semantics-free keyword searches or coarser grained file name searches. In this paper, we present an ontology based semantic query routing algorithm that performs efficient semantic search in unstructured P2P overlay networks. In our proposed system, the queries are routed in the network by forwarding to peers with highly relevant content in their local storages. To aid in this semantic query routing, we propose a scheme where each peer in the network adheres to a global ontology and semantically tags its local document collection with concepts in the ontology. Based on the semantic tags, peer level semantic summaries are generated, exchanged with neighboring peers and propagated along search paths which aid in efficient local query processing and overlay query routing. An extensive set of simulations performed to evaluate the effectiveness of the system on P2P networks show 380% and 717% improvement in average recall rate, and 410% and 725% improvement in average precision over Ontology Index based Query Routing [20] and Random Walk [18], respectively for dynamic networks at comparable message overheads. Thus, our approach represents a significant advance in practical terms.

Bilateral filtering is an ubiquitous tool for several kinds of image processing applications. This work explores multicore and many core accelerations for the embarrassingly parallel yet compute-intensive bilateral filtering kernel. For many core architectures, we have created a novel pair-symmetric algorithm to avoid redundant calculations. For multicore architectures, we improve the algorithm by use of low-level single instruction multiple data (SIMD) parallelism across multiple threads. We propose architecture specific optimizations, such as exploiting the unique capabilities of special registers available in modern multicore architectures and the rearrangement of data access patterns as per the computations to exploit special purpose instructions. We also propose optimizations pertinent to Nvidia's Compute Unified Device Architecture (CUDA), including utilization of CUDA's implicit synchronization capability and the maximization of single-instruction-multiple-thread efficiency. We present empirical data on the performance gains we achieved over a variety of hardware architectures including Nvidia GTX 280, AMD Barcelona, AMD Shanghai, Intel Harper town, AMD Phenom, Intel Core i7 quad core, and Intel Nehalem 32 core machines. The best performance achieved was (i) 169-fold speedup by the CUDA-based implementation of our pair-symmetric algorithm running on Nvidia's GTX 280 GPU compared to the compiler-optimized sequential code on Intel Core i7, and (ii) 38-fold speedup using 16 cores of AMD Barcelona each equipped with a 4-stage vector pipeline compared to the compiler-optimized sequential code running on the same machine.

No abstract available.

Data aggregation is an essential yet time-consuming task in wireless sensor networks (WSNs). This paper studies the well-known Minimum-Latency Aggregation Schedule (MLAS) problem and proposes an energy-efficient distributed scheduling algorithm named Clu-DDAS based on a novel cluster-based aggregation tree. Our approach differs from all the previous schemes where Connected Dominating Sets or Maximal Independent Sets are employed. We prove that Clu-DDAS has a latency bound of 4R' + 2Delta - 2, where Δ is the maximum degree and R' is the inferior network radius which is smaller than the network radius R. Clu-DDAS has comparable latency as the previously best centralized algorithm E-PAS, while Clu-DDAS consumes 78% less energy as shown by the simulation results. Clu-DDAS outperforms the previously best distributed algorithm DAS whose latency bound is 16R' + Δ - 14 on both latency and energy consumption. On average, Clu-DDAS transmits 67% fewer total messages than DAS does. We also propose an adaptive strategy for updating the schedule to accommodate dynamic network topology.

One of the fundamental problems involving DNA sequences is to find high density segments of certain widths, for example, those regions with intensive guanine and cytosine (GC). Formally, given a sequence, each element of which has a value and a width, the maximum-density segment problem asks for the segment with the maximum density while satisfying minimum and possibly maximum width constraints. While several linear-time sequential algorithms have emerged recently due to its primitive-like utility, to our knowledge, no nontrivial parallel algorithm has yet been proposed for this topical problem. In this paper, we propose an O(log2n)-time CREW PRAM algorithm using n processors to solve the generalized maximum-density problem, with a minimum width constraint and non-uniform widths. Besides, we describe an efficient implementation of the parallel algorithm on manycore GPUs (nVIDIA GeForce GTX 280), taking advantage of the full programmability of CUDA. This algorithm can process up to million-size sequence within a second using an nVIDIA GeForce GTX 280, thus demonstrating the practicality of this algorithm as a basic primitive for scientists. This may also indicate suitability of modern GPU architectures as implementation platform for certain PRAM algorithms.

A key problem in Wireless Sensor Networks is that of scheduling sensors into sleep-sense cycles that maximize the lifetime of the network while ensuring coverage of a set of targets. This is a known NP-complete problem, due to the exponential number of possible ways to select a subset of sensors to turn on. Our earlier work had presented a unique model for this problem by introducing a lifetime dependency (LD) graph in which these possible cover sets are nodes and edges represent shared sensors between them. Using the graph properties, we presented a range of effective distributed heuristics. Even though the local subgraphs are practically tractable, their theoretically exponential growth has remained a persistent issue. In this paper, we present a theoretical model for representing this exponential space of possible cover sets that groups related covers together, thereby reducing this exponential space virtually to a linear one. We then present an equivalence class (EC) graph as a model for this reduction. We use these underlying theoretical properties to develop a smart linear time sampling algorithm of this exponential space. To demonstrate the effectiveness of our sampling technique, we employ the sampled localized LD subgraph as input to our previous heuristics. Simulation studies show about twofold speedup while reducing solution quality (network lifetime) only by under 10% when compared to our previous heuristics that operate on the exponential space. We also compare our algorithms to two other state-of-art greedy algorithms and show that ours still manage to achieve improvements of around 8-10% over them.

One of the key challenges in Wireless Sensor Networks (WSNs) is that of extending the lifetime of the network while meeting some coverage requirements. In this paper we present a distributed algorithmic framework to enable sensors to determine their sleep-sense cycles based on specific coverage goals. The framework is based on our earlier work on the target coverage problem. We give a general version of the framework that can be used to solve network/graph problems for which melding compatible neighboring local solutions directly yields globally feasible solutions. We also apply this framework to several variations of the coverage problem, namely, target coverage, area coverage and k-coverage problems, to demonstrate its general applicability. Each sensor constructs minimal cover sets for its local coverage objective. The framework entails each sensor prioritizing these local cover sets and then negotiating with its neighbors for satisfying mutual constraints. We introduce a dependency graph model that can capture the interdependencies among the cover sets. Detailed simulations are carried out to further demonstrate the resulting performance improvements and effectiveness of the framework.

Parallelization of sequential programs is often daunting because of the substantial development cost involved. Previous solutions have not always been successful, partly because many try to address all types of applications. We propose a platform for parallelization of a class of applications that have similar computational structure, namely graph-structured iterative applications. iC2mpi is a unique proof-of-concept prototype platform that provides relatively easy parallelization of existing sequential programs and facilitates experimentation with static partitioning and dynamic load balancing schemes. We demonstrate with various generic application graph topologies that our platform can produce good performance with very little effort. The iC2mpi platform has a good potential for further performance improvements and for extensions to related classes of application domains.

In collaborative applications, participants agree on certain level of secure communication based on communication policy specifications. Given secure communication policy specifications of various group members at design time, the minimum set of resources for a pair, called resolved policy level agreement (RPLA) is translated into appropriate security service implementations, for the pair-wise communication to take place. We propose a novel idea that the members may extend pair-wise communication quality through other trusted nodes whose communication resources offer more security. We propose a heuristic algorithm which finds the best quality of protection (QoP), a measure of the resistance to an attack, path through coalition of trusted nodes. The results from our experiments indicate a significant improvement in QoP in the range of 13% to 48% over pair-wise communications.

The primary goals in a synchronous collaborative editing system (CES) involve ensuring a high level of concurrent access while maintaining the properties of the CCI model. We revisit the idea of applying lock-based concurrency control algorithms to manage access to a shared document; this research overcomes the traditional problem of reduced concurrent access inherent in pessimistic concurrency control by dynamically managing the size of the portion of document locked based upon user demand, scaling up and down the lock granularity to accommodate user write requests. We present algorithms to efficiently maximize concurrent access while utilizing caching techniques to reduce communication costs. We also discuss how OT and other optimistic concurrency control techniques may be incorporated within our approach ? leveraging best practices of both techniques. We conclude with an analysis of the communication and computational costs of our approach and compare these costs to costs incurred using OT-based concurrency control.

The current state of the art of workflows over Web services employs a centralized composite process to coordinate the constituent Web services. Therefore, the coordinator process is complex, less scalable, and bulky. This paper introduces an architecture and a technique for distributing the centralized coordination logic of traditional workflows by (i) extending the stateless Web services into self-coordinating entities using coordinator proxy objects, and (ii) creating a workflow over these entities by interconnecting them into a distributed network of objects using Web bond primitives. Previously, we have developed Web bond primitives to enforce interdependencies among autonomous entities. We have designed and prototyped our BondFlow system, which provides a platform to configure such distributed workflows, producing coordination components with footprint small enough (around 150 KB) to be executed on a handheld

In this paper, we consider the problem of maximizing the lifetime of a target-covering sensor network in which each sensor can adjust its sensing range. The network model consists of a large number of sensors with adjustable sensing ranges being deployed to monitor a set of targets. Since more than one sensor can cover a target, in order to be energy efficient, one can activate successive subsets of sensors that cover all targets. This paper addresses the problem of maximizing the total lifetime of such an activation schedule. In contrast to the approach taken by Cardei et al. (2005), our formulation directly maximizes the network lifetime rather than maximizing the number of sensor covers. We give a mathematical model of this problem using a linear program with exponential number of variables and solve this linear program using the approximation algorithm of Garg-Konemann (1998). Our experimental results on simulated data show a 4times increase in lifetime when compared with the previous approach taken by Cardei et al. (2005)

We envision users discovering suitable Web objects and configuring them on-the-fly with their desired high-level application logic, with the programming and deployment carried out entirely on the Web. Easy configurability and interplay of Web entities implies evolution of a few common sense, yet powerful set of core primitives for effective coordination, akin in simplicity and strength to the HTTP protocol. Current Web services technology lacks Infrastructure support, theoretical sound fundamental framework for Web services coordination and composition, and easy use tools for Web application development. Our Web coordination bond system gears towards finding solutions to aforementioned research challenges.

We recently developed "system on mobile devices" (SyD) middleware for rapidly developing and deploying collaborative distributed applications over a collection of autonomous Web objects and data-stores, independent of the underlying device, data, or network. SyDListener is a key component of SyD middleware. SyDListener provides a set of interfaces and classes that allows distributed SyD-based application components to communicate seamlessly in mobile environments. SyDListener provides a uniform object view of the underlying server application and enables client applications to remotely invoke those methods using XML messages. SyDListener is implemented as a multi-threaded wrapper with simple persistence management and asynchronous invocation functionality for J2ME mobile information device profile (MIDP) on connected limited device configuration (CLDL) devices. We discuss the functionality, architecture, implementation, and performance of SyDListener. We believe it is the first comprehensive working prototype of its kind for Java-enabled handhelds with a small footprint of 10 KB.

Future Web applications will be more collaborative and will use the standard and ubiquitous Internet protocols. We have previously developed system on mobile devices (SyD) middleware to rapidly develop and deploy collaborative applications over heterogeneous and possibly mobile devices hosting web objects. In this paper, we present the software engineering methodology for developing SyD-enabled Web applications and illustrate it through a case study on a system of calendar application, with implementation on iPAQs and its performance metrics study. SyD-enabled Web objects allow us to create a collaborative application rapidly with limited coding. In this case study, the modular software architecture allowed us to hide the inherent heterogeneity among devices, data stores, and networks by presenting a uniform and persistent object view of mobile calendar objects interacting through XML/SOAP requests and responses. The performance results we obtained show that the application scales well as we increase the group size and adapts well within the constraints of mobile devices.

This paper describes the advantages of SyD (System on Mobile Devices), a middleware technology for mobile devices and e-services, in terms of technology and programming. Features of SyD are illustrated here through our prototype application, a complex communication system for a trucking fleet that operates an automated package delivery system. The fleet system has been implemented in three ways, with SOAP, with JDBC, and with SyD. Our implementation experience shows that SyD greatly simplifies coding by allowing heterogeneous devices, peer-to-peer communications, group transactions based on triggering events, and mobility support through proxies and directory service.

Data mining has a lot of e-commerce applications. The key problem is how to find useful hidden patterns for better business applications. For these problems, granular fuzzy Web intelligence techniques are used to implement the granular fuzzy Web data mining system for available historical data of the credit company customers. Fuzzy computing and granular computing are used to design the Web fuzzy-interval data mining system that can do fuzzy-interval data clustering under uncertainty.

We study the problem of assigning transmission ranges to the nodes of ad hoc wireless networks to minimize power consumption while ensuring network connectivity. We give an exact branch and cut algorithm based on a new integer linear program formulation solving instances with up to 35-40 nodes in 1 hour; a proof that min-power symmetric connectivity with asymmetric power requirements is inapproximable within factor (1 - /spl epsi/) ln |V| for any /spl epsi/ > 0 unless P = NP; an improved analysis for two approximation algorithms recently proposed by Calinescu et al. (TCS'02), decreasing the best known approximation factor to 5/3 + /spl epsi/; and a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms.

In parallel and distributed systems, an important issue in managing a decentralized task queue is load balancing among multiple processors. In this paper, we propose a scheme for this problem by using a symmetric broadcast network (SBN) which provides an efficient and robust communication pattern between processors. We compare the performance of SBN-based load balancing algorithm with randomization-based algorithm, gradient algorithm, and extended gradient algorithm on a broad range of computing and communication platforms. All four algorithms were first implemented on an 8-processor Intel's iPSC-2, a hypercube-based multicomputer. Then, the programs were ported to Parallel Virtual Machine (PVM). Using PVM we compared all four algorithms on (i) an d-processor bus-based Silicon Graphics multiprocessor (SGI), (ii) two DEC's Alpha workstations connected by a Local Area Network, and (iii) SGI and the two DEC Alpha's connected by internet. We found that our SBN-based algorithm performed well over a wide range of workloads, and computer and communication configurations.

We present four polylog-time parallel algorithms for matching parentheses on an exclusive-read and exclusive-write (EREW) parallel random-access machine (PRAM) model. These algorithms provide new insights into the parentheses-matching problem. The first algorithm has a time complexity of O(log/sup 2/ n) employing O(n/(log n)) processors for an input string containing n parentheses. Although this algorithm is not cost-optimal, it is extremely simple to implement. The remaining three algorithms, which are based on a different approach, achieve O(log n) time complexity in each case, and represent successive improvements. The second algorithm requires O(n) processors and working space, and it is comparable to the first algorithm in its ease of implementation. The third algorithm uses O(n/(log n)) processors and O(n log n) space. Thus, it is cost-optimal, but uses extra space compared to the standard stack-based sequential algorithm. The last algorithm reduces the space complexity to O(n) while maintaining the same processor and time complexities. Compared to other existing time-optimal algorithms for the parentheses-matching problem that either employ extensive pipelining or use linked lists and comparable data structures, and employ sorting or a linked list ranking algorithm as subroutines, the last two algorithms have two distinct advantages. First, these algorithms employ arrays as their basic data structures, and second, they do not use any pipelining, sorting, or linked list ranking algorithms.>