Online learning is useful for expanding educational offerings. This is crucial for institutions with limited space and courses with high demand. Universities still need to be mindful about the quality of their online offerings, and ensure that it meets higher education standards. In this work we present a retrospective comparison between concurrent offerings (one online and one in classroom) of a discrete math course. The online course was carefully designed to be as challenging as the classroom one. We note the key takeaways from the experience.

This paper proposes a distributed flow-based routing technique in energy-harvesting wireless sensor networks (EHWSNs) in order to balance the energy consumptions by sending packets assigned to routers that are sent from sensors to base stations. The objective of the flow optimization problem is to minimize the total load factors of all the nodes and wireless links, which leads to sustainable management of the sensor networks that exploit renewable power from energy harvesting systems. We propose a novel algorithm based on tie-set graph theory where the underlying graph of an EHWSN is divided into a set of independent loops to significantly reduce the topological complexity, which simplifies the flow optimization problem to be solved in a distributed manner. Simulation experiments against the shortest-path and multi-path algorithms demonstrate that optimized packet flows by the proposed method realize the sustainable EHWSNs and maintain the useful life of storage devices with modest increase in total energy consumption by routings.

Scientific computing is only bound by the limits of Moore's Law and the scalability of high performance mathematical library implementations. Most mathematical libraries however tend to focus only on general inputs, limiting their potential performance and scalability by not tailoring their implementation to specific inputs, such as non-negative inputs. By removing this limitation it is possible to improve the performance and accuracy of a range of problems. In this paper we explore the limitations of hardware to improve accuracy of non-negative matrix multiply by specifically comparing implementations on the GPU and CPU and propose algorithmic solutions to improve accuracy. Next, we demonstrate a matrix multiply implementation that takes advantage of asymptotically fast matrix multiply algorithms, which have been shown to scale better than O(N3) matrix multiply implementations, and improve accuracy by up to a whole digit while increasing performance by up to 27% for matrices where the input is positive. Finally, we propose to extend the BLAS level 3 specification to non-negative matrices to allow easy integration of our solution and allow other library authors to implement their own solutions as part of an existing standard.

In this paper, we propose a mechanism for coping with double-link failures in an autonomous and distributed manner. We call it Tie-set Based Fault Tolerance (TBFT) because it utilizes tie-sets, which represent a set of the edges comprising a loop within the graph that represents the network. An autonomous distributed control method based on dividing a network into a set of tie-sets, whose union covers every edge in the network, has been verified to be more effective than traditional tree-based restoration techniques in case of single link failure. The proposed method efficiently and gracefully handle double-link failures and also decrease the communication overhead incurred during network configuration. We demonstrate these results by simulating and comparing TBFT with the traditional approach of using Rapid Spanning Tree Protocol (RSTP).

We present a new methodology for developing parallel distributed programs in a series of incremental steps. The methodology takes advantage of threads that are able to migrate through the network and thus are able to follow distributed data. This allows the data to be partitioned and distributed first, which guarantees that elements that are used together in a computation are collocated on the same node. Next, the loops in the code are tiled to minimize migration among nodes. After deciding on the location at which each loop is to execute, the necessary migration and remote access statements are inserted to make the code executable. This process is repeated based on feedback obtained from the execution, which may improve the overall performance by suggesting a different data distribution or a different coarseness of tiling. We illustrate the trade-offs and the performance using a well-known application with two different data distributions.

Matrix multiply is ubiquitous in scientific computing. Considerable effort has been spent on improving its performance. Once methods that make efficient use of the processor have been exhausted, methods that use less operations than the canonical matrix multiply must be explored. Combining the two methods yields a hybrid matrix multiply algorithm. Hybrid matrix multiply algorithms tend to be less accurate than the canonical matrix multiply implementation, leaving room for improvement. There are well-known techniques for improving accuracy, but they tend to be slow and it is not immediately obvious how best to apply them to hybrid algorithms without lowering performance. Previous attempts have focused on the bottom of the hybrid matrix multiply algorithm, modifying the high-performance matrix multiply implementation. In contrast, the top-down approach presented here does not require the modification of the high-performance matrix multiply implementation at the bottom, nor does it require modification of the fast asymptotic matrix multiply algorithm at the top. The three-level hybrid algorithm presented here not only has up to 10% better performance than the fastest high-performance matrix multiply, but is also more accurate.

With systems such as Road Runner, there is a trend in super computing to offload parallel tasks to special purpose co-processors, composed of many relatively simple scalar processors. The cheaper commodity class equivalent of such a processor would be the graphics card, potentially offering super computer power within the confines of a desktop PC. Graphics cards however are not without problems, these range from the lack of double precision on most cards to a fairly steep drop in performance for using double precision on others, the end result being that in order to utilize the graphics card the computation must be done using single precision. In this paper we propose a method whereby a whole digit of the accuracy lost in single precision matrix multiply can be regained with only a 7% loss in performance by applying a compensated summation algorithm in a manner previously unexplored, a manner in which, at first glance, shouldn't provide any benefit but empirical evidence will show that though the novel idea is simple, provides unexpected benefits in terms of accuracy at little cost to performance.

We present an approach to implementing and using global pointers in a distributed computing environment. The programmer is able to create pointer-based distributed data structures, which can then be used by sequential or parallel programs without having to differentiate between local and global pointers. Any reference to a remote address causes the process to either migrate to the remote host, where it continues its execution, or to perform a remote access operation. The decision is made automatically and fully transparently to the programmer. By using a hardware-supported memory checking mechanism, we avoid any overhead associated with the detection of remote references.

Program parallelization requires mapping computation and data to processing elements. Navigational Programming (NavP), based on the principle of migrating computations, offers a different approach than the conventional solutions that use a SPMD model. This paper focuses on data distribution for NavP. We introduce the Navigational Trace Graph (NTG), a mathematical structure that captures the alignment and distribution preferences of a sequential program. Graph partitioning is applied to NTGs to obtain data distribution solutions. The major advantage is that our methodology can focus exclusively on reducing communication overhead first and later determine the actual computation partition and parallelization, because NavP computations migrate freely across partitions. This is in stark contrast to SPMD, where the data partitioning imposes hard constraints on the threads because they are stationary. We present experimental results to demonstrate the effectiveness of our approach.

We show how a series of transformations can be applied to incrementally parallelize sequential programs. Our navigational programming (NavP) methodology is based on the principle of self-migrating computations and is truly incremental, in that each step represents a functioning program and every intermediate program is an improvement over its predecessor. The transformations are mechanical and straightforward to apply. We illustrate our methodology in the context of matrix multiplication. Our final stage is similar to the classical Gentleman's algorithm. The NavP methodology is conducive to new ways of thinking that lead to ease of programming and high performance.

We describe an environment for the distributed solution of iterative grid-based applications. The environment is built using the MESSENGERS mobile agent system. The main advantage of paradigm-oriented distributed computing is that the user only needs to specify the application-specific sequential code, while the underlying infrastructure takes care of the parallelization and distribution. The two paradigms discussed in this papers are: the finite difference method, and individual-based simulation. These paradigms present some interesting challenges, both in terms of performance (because they require frequent synchronized communication between nodes) and in terms of repeatability (because the mapping of the user space onto the network may change due to load balancing or due to changes in the underlying logical network). We describe their use, implementation, and performance within a mobile agent-based environment.

Sequential computations can benefit from a distributed environment consisting of a network of workstations through the use of a mobile agent system. We found significant performance improvement when sequential algorithms for solving large industrial problems are implemented using mobile agents. This is because raw data is distributed so that the cost of disk paging is completely eliminated, and a principle of "code moving to data" is followed to achieve efficient communication through the network. We argue that mobile agent systems provide a new level of abstraction in which application programming is made easier because the sequential algorithms remain essentially unchanged in mobile agent code.

This paper proposes a new approach to rollback-recovery for mobile agent systems, and describes its implementation in the MESSENGERS mobile agents system. The used checkpointing method allows the implementation of a space and time efficient, user-transparent rollback-recovery in heterogeneous distributed environments. Together with an efficient non-blocking system snapshot algorithm this checkpointing method is an attractive choice for implementing a rollback-recovery mechanism in a mobile agent system, because it exploits features specific to such systems during the recovery. This paper also presents an optimization technique, called concurrent checkpointing, that increases the effectiveness of the proposed rollback-recovery mechanism.

We describe the implementation underlying an environment for distributed computing that uses the concept of well-known paradigms. The main advantage of paradigm oriented distributed computing is that the user only needs to specify application-specific sequential code, while the underlying infrastructure takes care of the parallelization and distribution. The main features of the proposed approach, called PODC, which differentiate it from other approaches, are the following: (1) it is intended for loosely-coupled network environments, not specialized multiprocessors; (2) it is based on an infrastructure of mobile agents; (3) it supports programming in C, rather than a functional or special-purpose language, and (4) it provides a Web based interactive graphics interface through which programs are constructed, invoked, and monitored. The three paradigms presently supported in PODC are the bag-of-tasks, the branch-and-bound and genetic programming. We describe their implementation and performance within the mobile agent based PODC environment.

Systems with global spares, in which a spare can replace any of multiple identical primary modules, are widely used. We present efficient algorithms for approximating the probability distribution of performance level (number of working modules) in systems with global spares and arbitrary module failure distribution. For nondegradable systems with global spares and arbitrary module failure distribution, our algorithms provide the first efficient solution for reliability. For degradable systems with global spares, our algorithms can be used to produce upper and lower bounds on various dependability measures.

This paper presents a new checkpointing algorithm that guarantees the semantics of reliable communication channels despite the crash and recovery of processes. This algorithm requires O(n+m) communication messages, where n is the number of participating processes, and m is the number of "late" messages. The algorithm is nonblocking, requires minimal message logging, and has minimal stable storage requirements. This algorithm is also scalable, simple transparent to the user, and facilitates fast recovery. By introducing suitable delay in the checkpointing process, the parameter m can be made small. We also describe a variant of the algorithm that requires only O(n) messages, at a cost of O(n) additional storage for each process.

Messengers are autonomous objects, each capable of navigating through the underlying network and performing various tasks at each node. Messenger applications are written using navigational commands rather than the send/receive primitives of conventional message-passing approaches. In this paper we contrast the two programming styles. The navigational style generally results in a smaller semantic gap between abstract algorithm descriptions and their actual implementations, which makes programs easier to construct, understand, and maintain. Other advantages of the navigational programming style include the ability to compute in unknown or dynamically changing network topologies.

Most research on semantic integrity has taken place in the traditional database fields, specifically the relational data model. Advanced models, such as semantic and object-oriented data models, have developed higher level abstractions to increase their expressive power in order to meet the needs of newly emerging application domains. This allows them to incorporate some semantic constraints directly into their schemas. There are, however, many types of restrictions that cannot be expressed solely by these high-level constructs. Therefore we extend the potential of advanced models by augmenting their abstractions with useful set restrictions. In particular, we identify and formulate four of their most common semantic groupings: set groupings, is-a related set groupings, power set groupings, and Cartesian product groupings. For each, we define a number of restrictions that control its structure and composition. We exploit the notion of object identity for the definition of these semantic restrictions. This permits each grouping to capture more subtle distinctions of the concepts in the application environment, as demonstrated by numerous examples throughout this paper. The resulting set of restrictions forms a general framework for integrity constraint management in advanced data models.>

This paper presents a Data-Distributed Execution (DDE) approach that exploits iteration-level parallelism in loops operating over arrays.

The EM-4 is a supercomputer that offers very fast interprocessor communication and support for multithreading. In this paper we demonstrate that the EM-4, together with an automatic parallelization technique referred to as Data-Distributed Execution (DDE), offer a computing environment in which large portions of scientific code can be executed without the need for any explicit parallelism.

The authors point out that in functional modeling, the functionalities of one or more components, like arithmetic/logic units, memories, and counters, are described as separate concurrent blocks. An algorithm, called the functional synthesis algorithm (FSA), for synthesis from these functional descriptions is presented. The algorithm automatically synthesizes components needed to implement a functional description while minimizing hardware costs and performance. Since a functional description uses standard operators in the hardware description language, a mismatch between the operators of the language and the functionalities provided by library components arises. FSA solves this functionality mismatch problem by pattern matching between the description and a library of function patterns. In addition, FSA clusters functions to maximally match components from a given library. Experimental results show that automated functional synthesis produces designs that are comparable to those produced by human designers.>

An approach to extracting iteration-level parallelism from dataflow programs is presented. The method exploits the single-assignment principle, which guarantees that any data value has exactly one producer. To minimize interprocessor communication, the code is modified so that, at run time, each producer executes on the processor that holds the corresponding data. Overhead resulting from possibly remote read accesses is alleviated by a software technique similar to caching. The performance of this process-oriented dataflow system (PODS) is demonstrated using the hydrodynamics simulation benchmark called SIMPLE, in which a 19-fold speedup on a 32-processor architecture has been achieved.>

The semantics of set operations are not adequate for the richer data models of object-based database systems that include object-oriented and semantic data modeling concepts. The reason is that precise semantics of set operations on complex objects require a clear distinction between the dual notions of a set and a type, both of which are present in the class construct found in object-based data models. This gap is filled here by a framework for executing set theoretic operations on the class construct. The proposed set operations, including set difference, union, intersection and symmetric difference, determine both the type description of the derived class as well as its set membership. For the former, inheritance rules are developed for property characteristics such as single-valued versus multivalued and required versus optional. For the latter, the object identity concept is developed if borrowed from data modeling research. The framework allows for property inheritance among classes that are not necessarily IS-A related.>

Three of the most common fundamental groupings that are utilized in semantic database models are considered: set groupings, power set groupings, and Cartesian aggregation groupings. For each, useful restrictions that control its structure and composition are defined. This permits each grouping to capture more subtle distinctions of the concepts or situations in the application environment. The resulting set of restrictions forms a framework for integrity constraints in semantic data models. This framework is targeted towards advanced applications, such as computer-aided design, office automation, and artificial intelligence, which require the support of more sophisticated relationships among data than traditional database domains.>

In functional modeling, one or more micro-architecture components are described as separate concurrent blocks. An algorithm, called the component synthesis algorithm, is presented that automatically synthesizes micro-architecture components for a functional description. Experimental results show that the automated functional synthesis is comparable to the performance of human designers.>

The Process-Oriented Dataflow System (PODS) is an execution model that combines the von Neumann and dataflow models of computation to gain the benefits of each. Central to PODS is the concept of array distribution and its effects on partitioning and mapping processes. The authors present and discuss the results of executing the classic matrix multiply algorithm (with 1024 data points) on a PODS simulator. The key result is that PODS can take advantage of the parallelism in matrix multiply using a simple automated partitioning scheme.>

A message-driven model for function-free Horn logic is presented, where the knowledge base is represented as a network of logical processing elements communicating with one another exclusively through messages. The lack of centralized control and centralized memory makes this model suitable for implementation on highly parallel asynchronous computer architecture. The performance of this message-driven system is analyzed and compared to that of a sequential resolution scheme using backtracking. Closed-form expressions for both approaches are derived.>

The binary predicate execution model (BPEM) is a computational model that combines logic programming, semantic nets, and message-driven computation into a paradigm for the construction of highly parallel knowledge-base systems. Simulation results are presented that demonstrate the ability of BPM to exploit effectively the resources of a loosely coupled computer network consisting of large numbers of independent processing elements. These simulations suggest performance on the order of 10/sup 5/ logical inferences per second for 256 processing elements in an n-cube configuration. A very important feature of the BPEM is that it scales-up linearly under simple OR-parallelism and AND-parallelism. Hence, the BPEM can scale-up to exploit parallelism efficiently in very large semantic networks and knowledge bases.>

Loosely-coupled MIMD architectures do not suffer from memory contention; hence large numbers of processors may be utilized. The main problem, however, is how to partition data and programs in order to exploit the available parallelism. In this paper we show that efficient schemes for automatic data/program partitioning and synchronization may be employed if single assignment is used. Using simulations of program loops common to scientific computations (the Livermore Loops), we demonstrate that only a small fraction of data accesses are remote and thus the degradation in network performance due to multi-processing is minimal.

In recent years, a number of database machines consisting of large numbers of parallel processing elements have been proposed. Unfortunately, there are two main limitations in database processing that prevent a high degree of parallelism; these are the available I/O bandwidth of the underlying storage devices and the concurrency control mechanisms necessary to guarantee data integrity. The main problem with conventional approaches is the lack of a computational model capable of utilizing the potential of any significant number of processing elements and storage devices and, at the same time, preserving the integrity of the database. This paper presents a database model and its associated architecture, which is based on the principles of data-driven computation. According to this model, the database is represented as a network in which each node is conceptually an independent, asynchronous processing element, capable of communicating with other nodes by exchanging messages along the network arcs. To answer a query, one or more such messages, called tokens, are created and injected into the network. These then propagate asynchronously through the network in search of results satisfying the given query. The asynchronous nature of processing permits the model to be mapped onto a computer architecture consisting of large numbers of independent disk units and processing elements. This increases both the available I/O bandwidth as well as the processing potential of the machine. At the same time, new concurrency control and error recovery mechanisms are necessary to cope with the resulting parallelism.

There is a direct correspondence between semantic networks and a subset of logic programs, restricted only to binary predicates. The advantage of the latter is that it can describe not only the nodes and arcs comprising a semantic net, but also the data-retrieval operations applied to such nets. The main objective of this paper is to present a data-driven model of computation that permits this subset of logic programs to be executed on a highly parallel computer architecture. We demonstrate how logic programs may be converted into collections of data-flow graphs in which resolution is viewed as a process of finding matches between certain graph templates and portions of the data-flow graphs. This graph fitting process is carried out by messages propagating asynchronously through the data-flow graph; thus computation is entirely data driven, without the need for any centralized control and centralized memory. This permits a potentially large number of independent processing elements to cooperate in solving a given query.

Logic programming is a mathematical formalism capable of expressing certain classes of problems in a non-procedural manner. Furthermore, logic programs do not presuppose a von Neumann computer architecture and are therefore inherently well suited to parallel computations. In this paper we consider a data-driven model for interpreting logic programs and investigate the architectural requirements necessary to support its implementation. It will be shown that the model is capable of exploiting the capabilities of highly-parallel dataflow architectures.