Digitized by Kansas Correctional Industries

Digitized by Kansas Correctional Industries

An 8 bit microcontroller slave unit was designed, constructed, and tested to demonstrate advantages and feasibility of master/slave parallel processing using conventional processors and relatively slow inter-processor communications. An 8 bit ISA bus controlled by an 80X86 is interfaced to a logic block that controls data flow to and from the slave processors. The slave processors retrieve tasks sent by the master processor and once completed, return results to the master that are buffered for the master's retrieval. The task message sent to the slave processors has task description and task parameters. The master has access to the bi-directional buffer and a status byte for each slave processor. Considerable effort is made to allow the hardware and software architecture to be expandable such that the general design could be used on different master/slave targets. Attention is also given to cost effective solutions such that development and possible market production can be considered. / Graduation date: 1999

M.S. / Computer Science & Engineering / A study was made of some of the characteristics, capabilities, and limitations of the iPSC concurrent computer manufactured by the Intel Corporation. Initial experiments with test programs measured the large amount of time required to send and receive messages between nodes and between the cube manager and the nodes. Programs adapted to run concurrently will have the greatest speedup over the same program executed serially if the computational time is large relative to the time spent passing messages. A large-scale computational chemistry program (named ECEPP83) that calculates the global minimum energy of peptide structures (a peptide is a small protein) was ported and adapted to execute on the iPSC computer. The data entry and checking portion of the original code was ported to the 286/310 Intel computer that serves as a manager of the 32 to 128 CPU's (nodes) of the iPSC. The data for each structure is sent by the manager to a separate node which reports its results back to the host or system manager and then is assigned another structure. This adaptation is able to concurrently minimize the energy for 32 chemical structures a maximum of approximately 17 times faster than the same data can be utilized serially on a VAX 11-780 computer. A user manual was written to assist the user in assembling the input data file.

Thesis (Ph. D.)--University of Washington, 2001. / Vita. Includes bibliographical references (leaves 209-217).

Thesis (Ph. D.)--Lehigh University, 2003. / Includes vita. Includes bibliographical references (leaves 295-300).

Estimating the sortedness of a sequence has found applications in, e.g., sorting algorithms, database management and webpage ranking. As the data volume in many of these applications is massive, recent research has been focusing on estimating sortedness in the data stream model. In this thesis, we extend the study of this problem to a number of directions. One common measurement of sortedness is the edit distance to monotonicity. Given a stream of items drawn from a totally ordered set, its edit distance to monotonicity is the minimum number of items to remove so that the remaining items are non-decreasing. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming well-understood over the past few years. Motivated by applications on network quality monitoring, we extend the study to estimating the edit distance to monotonicity of a sliding window covering the w most recent items in the stream for any w _ 1. We give a deterministic algorithm which can return an estimate within a factor of (4 + _) using O( 1 _2 log2(_w)) space. We further extend the study in two directions. First, we consider a stream where each item is associated with a value from a partially ordered set. We give a randomized (4+_)-approximate algorithm using O( 1_2 log _2w log w) space. Second, we consider an out-of-order stream where each item is associated with a creation time and a numerical value, and items may be out of order with respect to their creation times. The goal is to estimate the edit distance to monotonicity with respect to the numerical value of items arranged in the order of creation times. We show that any randomized constant-approximate algorithm requires linear space. Finally, we revisit the classical problem of estimating the length of the longest increasing subsequence (LIS) of a data stream. Previous work shows that any deterministic algorithm requires ?(pN) space through a communication problem Hidden-IS, where N is the number of items in the stream. But the randomized space complexity of LIS is open [2]. [23] has given an efficient randomized protocol for Hidden-IS, showing that Hidden-IS may be significantly easier than LIS. We give an even simpler and more efficient randomized protocol for the Hidden-IS problem, indicating that it is unlikely that this communication problem can lead to a polynomial randomized space lower bound for the LIS problem. On the positive side, we propose a new communication problem which we conjecture to be hard enough to lead to a super polylogarithmic randomized space lower bound for the LIS problem. / published_or_final_version / Computer Science / Master / Master of Philosophy

No description available.

No description available.

No description available.