The mathematical contents of scientific publications in PDF format cannot be easily analyzed by regular PDF parsers and OCR tools. In this paper, we propose a novel OCR system called PDF2LaTeX, which extracts math expressions and text in both postscript and image-based PDF files and translates them into LaTeX markup. As a preprocessing step, PDF2LaTeX first renders a PDF file into its image format, and then uses projection profile cutting (PPC) to analyze the page layout. The analysis of math expressions and text is based on a series of deep learning algorithms. First, it uses a convolutional neural network (CNN) as a binary classifier to detect math image blocks based on visual features. Next, it uses a conditional random field (CRF) to detect math-text boundaries by incorporating semantics and context information. In the end, the system uses two different models based on a CNN-LSTM neural network architecture to translate image blocks of math expressions and plaintext into the LaTeX representations. For testing, we created a new dataset composed of 102 PDF pages collected from publications on arXiv.org and compared the performance between PDF2LaTeX and the state-of-the-art commercial software InftyReader. The experiment results showed that the proposed system achieved a better recognition accuracy (81.1%) measured by the string edit distance between the predicted LaTeX and the ground truth.

Mathematical objects (MO) in PDF documents is paramount in understanding the ontology and mathematical essence in published science, technology, engineering, and mathematical (STEM) documents. As of now, Marmot is the only publicly available data set for optimizing and evaluating MO labeling models in PDF documents. Thus, this paper proposes a semiautomatic labeling MO algorithm that uses PDF documents and their corresponding LaTeX source files to generate a new data set consisting of MO bounding boxes (Bbox) in PDF documents, their LaTeX equation, topic, and subject. The first step in labeling each MO is to transform the LaTeX and PDF documents into a string format. Afterwards, a shortest unique string-matching technique is proposed to align PDF pages with LaTeX files. On each page, a similar shortest string-matching technique is employed to align each LaTeX MO with its PDF counterpart. Once an MO is located, the PDF and LaTeX MOs are normalized in order to match symbols between their LaTeX and PDF representations. A number of filtering rules are set to eliminate matches that are considered exceedingly inconsistent. Matches that pass these rules will have their MOs highlighted for final manual inspection. A total of 1,802 pages in the high energy physics (hep-th) field were labelled.1

Mathematical expressions (ME) and words are carefully bonded together in most science, technology, engineering, and mathematics (STEM) documents. They respectively give quantitative and qualitative descriptions of a system model under discussion. This paper proposes a general model for finding the co-reference relations between words and MEs, based on which we developed a novel algorithm for predicting the natural language declarations of MEs--the ME-Dec. The prediction algorithm is applied in a three-level framework, where the first level is a customized tagger to identify the syntactic roles of MEs and the part-of-speech (POS) tags of words in the ME-word mixed sentences. The second level screens the ME-Dec candidates based on the hypothesis that most ME-Dec are noun phrases (NP). A shallow chunker is trained from the fuzzy process mining algorithm, which uses the labeled POS tag series in the NTCIR-10 dataset as input to mine for the frequent syntactic patterns of NP. In the third level, using distance, word stem, and POS tag respectively as the spatial, semantic, and syntactic features, the bonding model between MEs and ME-Dec candidates is trained on the NTCIR-10 training set. The final prediction results are made upon the majority votes of an ensemble of Naïve Bayesian classifiers based on the three features. Evaluation of the model on the NTCIR-10 test set, the proposed algorithm achieved 75% and 71% average F1 score in soft matching and strict matching, respectively, which outperforms the state-of-the-art solutions by a margin of 5-18%.1

This paper proposes a multi-stage architecture to extract math expressions (ME) from PDF documents based on font analysis. The unsupervised algorithm starts from symbol level analysis based on metadata of PDF objects, including font size, font name, and glyph name. Two subsequent stages utilize a group of spatial and semantic heuristics to merge multiple ME symbols into both inline ME and displayed ME. The algorithm is tested on the Marmot dataset (amended with missing cases). For displayed ME, the proposed method achieved 93.6% precision, 99.4% recall, and 96.4% F1-score. For inline ME, the method achieved 92.2% precision, 91.9% recall, and 92.1% F1-score. In addition, the algorithm only takes an average of 1.09s to process a page, which is faster than other existing methods.

Inline Mathematical Expression refers to Math Expression (ME) that is blended into plaintext sentences in scientific papers. Detecting inline MEs is a non-trivial problem due to the unrestricted usage of font styles and blurred boundaries with plaintext in scientific publications. For instance, many inline MEs detected by existing algorithms are split into multiple parts incorrectly due to the misidentification of a few characters. In this paper, we propose a bigram regularization model to resolve the split problem in inline ME detection. The model incorporates neighboring constraints during labeling of ME vs. plaintext. Experimental results show that this technique significantly reduces the splits of inline MEs, with small gains in the false and miss rate. In comparison with a CRF model, our model achieves a higher F1 score and a lower miss rate.

This paper presents a novel geometric model to characterize the zero-crossing surface (z-surface) and its z-curve for signals emitted by a pair of Global Navigation Satellite System satellites (A, B). The z-surface is the surface of points which have zero difference in pseudorange to (A, B), and the z-curve is the intersection of z-surface with the earth's surface. As a form of time difference of arrival, modeling of the z-surface/z-curve benefits from the elimination of common error terms (e.g., receiver clock offset) shared by the pair of pseudoranges, so that the resulting model can be used for design of advanced applications, such as timing and positioning integrity monitors and tools for geodetic and atmospheric measurements. The derivation of the z-curve starts with the shape modeling of the terrestrial service volume and the earth's surface. Then, an equi-pseudorange surface of (A, B)'s signals can be placed within these shape models. The z-curve can be derived as a boundary condition of the z-surface. The model can represent the morphing of z-curves with respect to the changes in satellite positions and signal propagation delays. As a result, the z-models can be readily generalized into a k-surface and k-curve, where k represents the pseudorange difference between (A, B). Solutions for modeling and analysis of the z(k)-surface/curve are based on a system of quadratic Cartesian equations. We propose an algebraic method to parameterize them in terms of geocentric latitude and longitude.

This paper presents two different prediction models of Mathematical Expression Constraints (ME-Con) in technical publications. Based on the assumption of independent probability distributions, two types of features: FS, based on the ME symbols; FW, based on the words adjacent to MEs, are used for analysis. The first prediction model is based on an iterative greedy scheme aiming to optimize the performance goal. The second scheme is based on naïve Bayesian inference of the two different feature types considering the likelihood of the training data. The first model achieved an average F1 scores of 69.5% (based on the tests made on an Elsevier dataset). The second prediction model using FS achieved 82.4% for F1 score and 81.8% accuracy. And it achieved similar yet slightly higher F1 scores as that of the first model for the word stems of FW, but slightly lower F1 score for the Part-Of-Speech (POS) tags of FW.1

Mathematical Expressions (ME) and words are carefully bonded in technical writing to characterize physical concepts and their interactions quantitatively, and qualitatively. This paper proposes the Qualitative-Quantitative (QuQn) map as an abstraction of scientific papers to depict the dependency among MEs and their most related adjacent words. QuQn map aims to offer a succinct representation of the reasoning logic flow in a paper. Various filters can be applied to a QuQn map to reduce redundant/indirect links, control the display of problem settings (simple ME variables with declaration), and prune nodes with specific topological properties such as the largest connected subgraph. We developed a visualization tool prototype to support interactive browsing of the technical contents at different granularities of detail.

This paper proposes a Font Setting based Bayesian (FSB) model to extract mathematical expressions (MEs) in the portable document format (PDF) files. The FSB model is a self-adaptive unsupervised algorithm which first uses rules to identify ME and non-ME (NME) and then extracts the remaining ME using the Bayesian inference based on the observation that MEs tend to repeatedly represented in a particular style. PDF files are first processed using a PDF parser and document layout is analyzed using projection profiling cutting based algorithm to detect columns and lines. Heuristic rules derived from the knowledge of math usage and writing practices are employed to reason about the posterior probability of a char being ME vs. NME, conditional upon the font and value information. Based on the char level posterior probability, Bayesian inference is used to infer a none-separable character set (NSCS) being ME or not. Consecutive (fragmented) ME NSCS are merged to produce final results. Experimental results show that our approach achieves 0.006 (0.135) false rate and 0.111/0.093 miss rate for IME (EME) extraction. As for NSCS classification, our approach achieves 93.1% precision, 90.5% recall rate, and F1 score of 0.918. The processing time is markedly shorter than supervised machine learning techniques, and the extracted information and analytics products can be used for high level applications.

We propose an FPGA-based high performance parallel architecture for music retrieval through singing. The database consists of monophonic MIDI files which are modeled into strings, and the user sung query is modeled as a set of regular expressions (regexp), with consideration of possible key transpositions and tempo variations to tolerate imperfectly sung queries. An approximate regexp matching algorithm is developed to calculate the similarity between a regexp and a string, using edit distance as the metrics. The algorithm supports user sung queries starting anywhere in the database song, not necessarily from the beginning. Using the proposed formal models and algorithms, the similarity between the user sung query and each song in the database can be evaluated and the top-10 most similar results will be reported. We designed the approximate regexp matching algorithm in such way that all terms of the regexp can execute concurrently, which perfectly fits the massive parallelism provided by FPGA. The FPGA implemented melody matching engine (MME) is a parameterized modular architecture that can be reconfigured to implement different regexps by simply updating their parameter registers, and can therefore avoid the time-consuming code re-synthesis. MME also includes an on-board DDR2 memory to store the database, so that they can be read in to calculate edit distances locally on the board. This way, each MME forms a self-contained system and multiple MMEs can be clustered to increase parallel processing power, with virtually no overhead. MME is evaluated using the query corpus of ThinkIT with 355 sung files and database of 5563 MIDI files. It achieves a top-10 hit rate of 90.7% and a runtime of 19.4 seconds, averaging 54.6 milliseconds for a single query. MME achieves significant speedup over software-based systems while providing the same level of flexibility.

We propose an NFA-based algorithm called MIN-MAX to support matching of regular expressions (regexp) composed of Character Classes with Constraint Repetitions (CCR). MIN-MAX is well suited for massive parallel processing architectures, such as FPGAs, yet it is effective on any other computing platform. In MIN-MAX, each active CCR engine (to implement one CCR term) evaluates input characters, updates (MIN, MAX) counters, and asserts control signals, and all the CCR engines implemented in the FPGA run simultaneously. Unlike traditional designs, (MIN, MAX) counters contain dynamically updated lower and upper bounds of possible matching counts, instead of actual matching counts, so that feasible matching lengths are compactly enclosed in the counter value. The counter-based design can support constraint repetitions of n using O({\rm log} n) memory bits rather than that of O(n) in existing solutions. MIN-MAX can resolve character class ambiguity between adjacent CCR terms and support overlapped matching when matching collisions are absent. We developed a set of heuristic rules to assess the absence of collision for CCR-based regexps, and tested them on Snort and SpamAssassin rule sets. The results show that the vast majority of rules are immune from collisions, so that MIN-MAX can cost effectively support overlapped matching. As a bonus, the new architecture also supports fast reconfiguration via ordinary memory writes rather than resynthesis of the entire design, which is critical for time-sensitive regexp deployment scenarios.

This paper proposes a multi-thread based regular expression (regexp) matching algorithm, M-DFA (multithreaded DFA), for parallel computer architectures such as multi-core processors and graphic processing units (GPU). At the thread level, one thread is designated to traverse the DFA of a possible matching path until its termination, and at the task level multiple threads concurrently match each input symbol in parallel. Given a set of regexps, the total number of (DFA) state transitions in M-DFA is significantly smaller than that of its traditional DFA counterpart. The significant saving of state transitions is contributed by elimination of backtracking transitions, which commonly occur to mapping of concurrent active states in NFA to DFA and other situations. Experimental result shows that the proposed algorithm achieves significant reduction on state and state transition. In addition, the proposed algorithm running on Nvidia® GTX 480 is 35 times faster than the popular regexp library, RE2 performed on Intel Core i7 CPU.

Existing cloud storage systems lack privacy aware architectures that meet accessibility goals for complex collaboration. This deficiency is fully realized in the healthcare industry, where cloud-enabling technology blurs the ownership boundary of health and wellness information. Whether among traditional `stovepiped' data silos, health information exchanges or personally controlled health information repositories, various forms of privacy neglect are common practice. We propose a paradigm shift in the interaction of users with cloud services that removes unwarranted trust in the cloud service provider and provisions accessibility for collaborators. To realize the paradigm shift, it is necessary to provide anonymity in data storage and separate the administration of access policy and authorization from the mechanisms used for enforcement. The dispensation of authorizations in the SAPPHIRE architecture bootstraps a traditional Kerberos ticket-based approach with `trust verifications'. In our evaluation, we prove the security properties of the SAPPHIRE architecture and implement a small scale prototype. Our analysis shows that SAPPHIRE is a viable extension of collaborative health information systems through the provision of anonymity and enhanced policy administration for the primary data owner.

We propose a non-deterministic finite automata (NFA) based architecture for regexp scanners on FPGA, called CES: the Character Class with Constraint Repetition (CCR) based regExp Scanner. CES is designed to realize a new MIN-MAX counting algorithm, which can solve both the character class ambiguity problem and the overlapped matching problem. CES also supports non-regular Perl grammars such as zero-width pattern and back-reference. We propose a CCR-syntax tree and its parsing scheme to map a Perl or POSIX regexp rule to a CES topology. The interconnection patterns, and operational parameters of CCR modules (CCRM), which are the building blocks of CES, can be easily configured by regular memory writes when regexp rules change, without re-synthesis of low-level logic.

In this paper, we propose a simple yet robust unsupervised algorithm for automated localization of macula-fovea area on retina images. The small sizes and weak contrast of the macula-fovea area on retina images make it unreliable to detect it directly. As such, we extract the retina blood vessel network topology based on local energy function of blood vessel widths and densities and use it as the main image cue to position the macula-fovea area. Regardless of the severity of most retinal diseases as well as variations in field clarity, the high level topology of the retinal blood vessel flows remains fairly predictable. Compared with conventional algorithms, our method can effectively localize the macula-fovea area on retina images with inadequate field clarity and diseased conditions. The algorithm is tested on both STARE and DRIVE retina image databases and gained satisfactory detection results.

In real-time systems, utilization-based schedulability test is a common approach to determine whether or not tasks can be admitted without violating deadline requirements. The test is extremely simple, since it only needs to compare the utilization of the tasks with a predetermined bound. As such, utilization-based schedulability tests are suitable for online use. The challenge is how to derive a reasonable utilization bound for a given system. Most existing results are obtained on a case-by-case basis because of their analytical complexity. In this paper, we develop a flexible and unified representation framework of real-time systems (i.e., tasks and schedulers) based on network calculus techniques. Our representation framework, together with the proposed bound derivation method, leads to a general bound result, which is applicable to a large family of real-time systems.

We propose a Progressive Email Classifier (PEC) for high-speed classification of message patterns that are commonly associated with unsolicited bulk email (UNBE). PEC is designed to operate at the network access point, the ingress between the Internet Service Provider (ISP) and the enterprise network; so that a surge of UNBE containing fresh patterns can be detected before they spread into the enterprise network. A real-time scoreboard keeps track of detected feature instances (FI) based on a scoring and aging engine, until they are considered either from valid or UNBE sources. A FI of a valid email is discarded, but an anomalous one is passed to a blacklist to control (e.g., block or defer) subsequent emails containing the FI.

In this paper, we proposed a novel algorithm to detect blood vessels on retinal images. By using directional local contrast as its detection feature, our algorithm is highly sensitive, fast and accurate. The algorithm only needs integral computing with very simple parameter adjustments and highly suitable for parallelization. It is much more robust to illumination conditions than intensity based counterparts and equally effective for large and small blood vessel detections. Traditional blood vessel mapping solutions focused on detecting the most number of blood vessel pixels at the cost of least number of falsely identified background pixels. This performance criterion works for well illuminated images with sharp boundary, but it does not address two major concerns. The first is that it favors detection of large blood vessels, and the second is that for darker images (due to poor illumination or pigment colors) it can be very difficult to generate hand traced maps. To overcome these problems, we propose using central lines of the blood vessels as a new performance measure for blood vessel mapping. The new performance measure is easy to evaluate, and it complements the existing performance measure. Experiment results on two public retinal image databases show that our algorithm outperforms two well known existing algorithms in terms of speeds and accuracy.

Schedulability analysis is a cornerstone of modern real-time scheduling theory development. Utilization- bound based schedulability test is considered one of most efficient and effective schedulability tests, because of its extremely low runtime overhead. Deriving the utilization bound for a given real-time system has, nevertheless, been a challenging task as it usually requires comprehensive modeling and understanding of the system and payload tasks. This paper is focused on deriving utilization bounds for weighted round robin schedulers. We demonstrate how to establish a unified modeling framework and then use it to derive utilization bounds. We obtain the optimal parameter selection that maximizes the utilization bound, then compare the new bound with those of fixed priority schedulers, and timed token ring schedulers. The new bound is further extended to systems with sporadic job requests. We argue that our modeling framework is highly versatile, and hence, can be easily tailored for analysis of other types of real-time systems.

While utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound itself. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this paper, we develop a general framework that allows one to effectively derive schedulability bounds for a wide range of real-time systems with different workload patterns and schedulers. Our analytical model is capable of describing a wide range of tasks and schedulers' behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform derivation of schedulability bounds. We derive a parameterized schedulability bound for static priority schedulers with arbitrary priority assignment. Existing utilization bounds for different priority assignments and task releasing patterns can be derived from our closed-form formula by simple assignments of proper parameters.

We propose a confidential logging and auditing service for distributed information systems. We propose a cluster-based TTP (trusted third party) architecture for the event log auditing services, so that no single TTP node can have the full knowledge of the logs, and thus no single node can misuse the log information without being detected. On the basis of a relaxed form of secure distributed computing paradigms, one can implement confidential auditing service so that the auditor can retrieve certain aggregated system information, e.g. the number of transactions, the total volume, the event traces, etc., without having to access the full log data. Similar to the peer relationship of routers to provide global network routing services, the mutually supported, mutually monitored cluster TTP architecture allows independent systems to collaborate in network-wide auditing without compromising their private information.

AIMD is a widely-used network congestion control scheme. Despite its discontinuous control behavior, the majority of contemporary literature employed a statistically-averaged continuous model to approximate AIMD without considering its discontinuity. The design of a discontinuous control system must be based on rules that are entirely different from that of continuous control systems. Ignoring discontinuity issues results in great discrepancy between analytical models and the practice. In this paper we use the sliding mode control (SMC) theory to investigate congestion control without ignoring its discontinuity. Based on the SMC theory, the design of discontinuous (congestion) control systems must consider the relative degree and zero dynamics of the system, in order to guarantee asymptotic stability. This framework can precisely reflect the behavior of the control rules and the controlled objective of a congestion control system. We show that the relative degree of the control system of rate-based, AIMD flow-control algorithms is two. That is, to apply sound control principles to the design of AIMD algorithms, one should use both the queue length error and its first order time derivative to construct the switching function of the control model of an active queue management scheme. Based on the SMC model, one can quantify the tradeoffs among the convergence speed, the amount of throttling adjustments, and the degree of oscillations. We show quantitatively that one can guarantee stability conditions, drastically reduce oscillation of AIMD without significant loss of fairness and stability, and quantitative understanding of the tradeoffs among oscillation, delay and fairness.

Estimation of the number of clusters is an essential processing step for various applications. Existing approaches search for an optimal solution by computing and comparing a validity measure for all feasible configurations, and tend to under-estimate the number of clusters incorrectly. We propose a fast and robust method to estimate the number of clusters without adopting an exhaustive search. Our scheme first extracts the relationship of neighboring features, and then uses this information to partition the clusters. The superb performance of the method is verified by the simulation results in determining the number of texture segments in textured images.

In this paper, we present a new rotation-invariant texture description scheme based on an explicit transform of texture features to shapes. Texture features are obtained in a short computational time by applying the partial form of Gabor functions. These features are then transformed to 2-D closed shapes, and their moment invariants and global shape descriptors are derived to classify the rotated textures. Experiments using various texture samples showed high rates of correct classifications.

In this paper, we propose a decision-based, signal-adaptive median filtering algorithm for removal of impulse noise. Our algorithm achieves accurate noise detection and high SNR measures without smearing the fine details and edges in the image. The notion of homogeneity level is defined for pixel values based on their global and local statistical properties. The cooccurrence matrix technique is used to represent the correlations between a pixel and its neighbors, and to derive the upper and lower bound of the homogeneity level. Noise detection is performed at two stages: noise candidates are first selected using the homogeneity level, and then a refining process follows to eliminate false detections. The noise detection scheme does not use a quantitative decision measure, but uses qualitative structural information, and it is not subject to burdensome computations for optimization of the threshold values. Empirical results indicate that our scheme performs significantly better than other median filters, in terms of noise suppression and detail preservation.

The explosive proliferation of networking technologies is drastically affecting operations in the health care industry. Physicians now can provide better services at lower costs through the efficient management of medical information. In recognition the importance of the interoperability of medical information, both government agencies and the private sector have made considerable investment in various medical standards, such as DICOM, HL7 and various electronic patient record systems. Among many of the standards activities, one missing element is a universal software model that would enable physicians to integrate and customize various medical information products into a complete suite for their particular needs. A software tool built on the basis of such a software model should be provably reliable, verifiable and field-configurable. It should allow instrument vendors to embed their hardware and software solutions into the tool without compromising their proprietary designs. This tool should be able to communicate and command different instruments in a consistent manner, so that new applications can be built upon well-known and well-accepted software layers. To demonstrate the effectiveness of this solution approach, we developed a portable medical information management prototype, the Portable Remote Diagnostic Information and Telemedicine System (PoRDITS).

This paper proposes a directional image force (DIF) for active contouring. DIF is the inner product of the zero crossing strength (ZCS) of wavelet frame coefficients, and the normal of a snake, by representing strength and orientation of edges at multiple resolution levels. DIF markedly improves the immunity of snakes to noise and convexity.

Texture boundaries or edges are useful information for segmenting heterogeneous textures into several classes. Texture edge detection is different from the conventional edge detection that is based on the pixel-wise changes of gray level intensities, because textures are formed by patterned placement of texture elements over some regions. We propose a prediction-based texture edge detection method that includes encoding and prediction modules as its major components. The encoding module projects n-dimensional texture features onto a 1-dimensional feature map through the SOFM algorithm to obtain scalar features, and the prediction module computes the predictive relationship of the scalar features with respect to their neighbors sampled from 8 directions. The variance of prediction errors is used as the measure for detection of edges. In the experiments with the micro-textures, our method has shown its effectiveness in detecting the texture edges.

This paper presents a decision-based median filtering algorithm in which local image structures are used to estimate the original values of the noisy pixels. The decision whether a pixel is corrupted or not is based on a new decision measure which considers the differences of adjacent pixel values in the rank-ordered sequence. Once the pixels in a noisy image have been classified into uncorrupted and noise-corrupted ones, the blocks containing only the uncorrupted pixels are used to train the predictive relationship between the center pixel and its neighbors, which is represented by a function approximation f. By applying f to noise-corrupted blocks, we could generate the candidates of the original value of a noise-corrupted pixel, and estimate it using median filtering of the candidates.

In this paper, we propose an unsupervised texture segmentation scheme in which Gabor transforms and GMRF model are integrated. The Gabor filters are used to extract low-level textural features. The Gabor feature vectors are mapped to an 1-D space using the Kohnen's SOFM algorithm, and then encoded by the feature map indices. The histogram of encoded features over a small window are used to determine the regions of homogeneous textures. From these regions, class-specific parameters for GMRF model are estimated and used to detect exact boundaries of different textures.

The paper presents linear time, online algorithms which guarantee and jointly schedule firm aperiodic, hard sporadic and periodic tasks in fixed priority real time systems. We develop and capitalize on a methodology which computes the spare capacity Z(a,b) exactly in time /spl Theta/(n), for arbitrary schedule intervals (a,b), which, to the best of our knowledge, is the first linear time algorithm reported in the literature. Previous state of the art methods incur pseudopolynomial time to guarantee online a single aperiodic and incur continuous overhead for slack maintenance. Our method guarantees and schedules firm tasks to receive FIFO or EDF service, incurring a one-time linear cost of /spl Theta/(n) and /spl Theta/(n+k) respectively, where k is the number of pending firm tasks.

This paper proposes a new parallelization of the Primal and Dual Simplex algorithms for Linear Programming (LP) problems on massively parallel Single-Instruction Multiple-Data (SIMD) computers. The algorithms are based on the Steepest-Edge pivot selection method and the tableau representation of the constraint matrix. The initial canonical tableau is formed on an attached scalar host unit, and then partitioned into a rectangular grid of sub-matrices and distributed to the individual Processor Element (PE) memories. In the beginning of the parallel algorithm key portions of the simplex tableau are partially replicated and stored along with the sub-matrices on each one of the PEs. The SIMD simplex algorithm iteratively selects a pivot element and carries-out a simplex computation step until the optimal solution is found, or when unboundedness of the LP is established. The Steepest-Edge pivot selection technique utilizes information mainly from local replicas to search for the next pivot element. The pivot row and column are selectively broadcasted to the PEs before a pivot computation step, by efficiently utilizing the geometry of the toroidal mesh interconnection network. Every individual PE maintains locally and keeps consistent its replicas so that inter-processor communication due to data dependencies is further reduced. The presence of a pipelined inteconnection network, like the mesh network of MP-1 and MP-2 MasPar models allows the global reduction operations necessary in the selection of pivot columns and rows to be performed in time O(log nR + log nC ), in (nR \\Theta nC ) PE arrays. This particular combination of pivot selection, matrix representation, and selective data replication is shown to be highly efficient in the solution of linear prog...

We propose the dynamic reconfiguration network (DRN) and a monitoring-at-transmission (MAT) bus to support dynamic reconfiguration of an N-modular redundancy multiprocessor system. In the reconfiguration process, a maximal number of processor triads are guaranteed to be formed on each processor cluster, thus supporting gracefully degradable operations. This is made possible by dynamically routing the control and clock signals of processors on the DRN so as to synchronize fault-free processors. The MAT bus is an efficient way to implement a triple modular redundant pipeline voter, which is a special case of the voting network proposed by Parhami (1991). Extensive experimental results have shown to support our design concept, and the performance of different cache memory organizations is evaluated through an analytic model.>

This paper proposes a fault-tolerant distributed subcube management scheme for hypercube multicomputer systems. Gracefully degradable subcube management is supported by a data structure, called the distributed subcube table (DST), and a fault-tolerant broadcast protocol, called the reliably synchronized broadcast (RSB). In an n-dimensional hypercube, DST is the collection of 2/sup n/ local subcube tables (LSTs), DST.>

This paper proposes a simple, yet effective scheme to prevent congestion in a packet-switched multistage interconnection network (MIN) caused by hot spots. In this scheme, switches in the second and third stages of the MIN monitor their buffer occupancy to detect any notable nonuniform access behavior. When a switch detects congestion, packets generated by processors will be blocked from entering the congested switch until the congestion is cleared. Our scheme is compared with two well known schemes and shown to exhibit significantly better performance than these two.>

This paper exploits the impact of the asynchronous transfer mode (ATM) transport standard on the mutual synchronization of multiple media servers in a distributed multimedia system. On the basis of a bursty traffic model, we develop and analyze an effective media synchronization scheme. In our scheme the media terminal (MT), which receives continuous streams of data from different media servers, acts as the coordinator for mutual synchronization of the media servers. The correlation between the time skew of clocks in the media servers and the network transmission behavior is analyzed, with the bursty traffic of the ATM network taken into account. We quantify the correlation between the resynchronization time interval, the clock drift rate, the time skew of servers, and the network jitter. Our results suggest that in allocation of ATM network resources to virtual channels (VC), the transmission delay, cell loss probability and synchronization of clocks are equally important in distributed multimedia systems.>

Proposes techniques to derive the worst-case execution time (WCET) of cached programs. We focus on the analysis of one single program run on a direct-mapped cache, where no external interference could occur. The analysis complexity of the WCET of (un)cached programs is NP-complete. For nested loops, we derive some sufficient conditions in deriving the deterministic bounds of their WCET. These sufficient conditions can be used to make trade-offs between tightness of the WCET bounds and their search time.>

This paper analyzes a load-balancing scheme, called All-Sharing Load Balancing (ASLB), which evenly distributes the load of the system among all nodes on a CSMA/CD local area network in a collision-free manner for each load-balancing activity. A novel analytical model is presented to evaluate performance of the ASLB scheme and its effect on the normal communication message transmission and vice versa. The evaluation also takes into account the tradeoff between system response time and message delay. Our analysis shows that ASLB can achieve good performance in both system response time and message transmission delay. Our analysis techniques are applicable to various distributed algorithms involved with interprocess coordination.

This paper proposes a novel distributed multicast algo rithm for hypercubes. Based on our algorithm, any node in a multicast-set can directly initiate a multicast to other nodes in the same set. The Dimension-PArtition Tech nique (DIPAT) is the underlying message routing tech nique. This routing technique is valid only for certain con nected graphs, called DIPAT-graphs whose necessary and sufficient conditions are derived. A heuristic algorithm is developed for construction of DIPAT-graphs. In addition, DIP AT is integrated with a simple spanning tree algorithm to form a hierarchical multicasting graph, which retains a higher level of distributed multicasting capability with a similar level of extra traffic as that of the existing single spanning tree based solutions.

A large-scale distributed computing system architecture for the area-wide real-time traffic control system (ARTC) of J.L. Kim et al. (1992) is presented. In the ARTC system, signal controllers coordinate with each other through the communications network to achieve real-time adaptive traffic control. For reliable service, the ARTC system is designed to be fault-tolerant at the I/O component, processor, and network levels. A modular system architecture that enables the ARTC signal controllers to support fault-tolerant design strategies is proposed. A flexible cost-effective networking strategy is presented to support different level network redundancy. In order to estimate the expected service quality of the ARTC control system and to study the reliability effects of signal controller failure rate, the repair efficiency, and the degree of system redundancy, an analytical model is developed.>

The authors present an efficient software application of a distributed system for area-wide traffic control. This system, called area-wide real-time traffic control (ARTC), can provide orderly movement of traffic, shorten average vehicle delay, prevent congestion, and improve road utilization. The signal controllers in ARTC, which are microcomputers, are interconnected through a computer network. By exchanging traffic flow information among the signal controllers, ARTC provides a novel concept in traffic control by using the computer network. Simulation results of the ARTC prototype control algorithm are presented. The results show substantial improvement over an optimized fixer time control. The signal controllers and the computer network were designed to support real-time communication requirements and a sufficient level of fault tolerance.>

A protocol for dynamic load balancing in distributed systems on the CSMA/CD local area network is presented. Using the protocol, the workload is evenly distributed throughout the system when load-balancing activity is triggered, and effective load distribution is accomplished through transmission of load-balancing messages in a collision-free manner. Analytical and simulation results are presented to show the efficiency of the protocol.>

A novel RAM architecture supporting concurrent memory access and on chip testing (CMAT) is proposed. A large-capacity memory chip is decomposed into test neighborhoods (TNDs), each of which is tested independently. When there are data stored in a TND, the data are saved into a buffer before testing the TND, and the TND's contents are restored using buffered data after testing the TND. If an external request is not made to the TND, the request can be directed to the addressed memory cells. Otherwise, the buffered data can be loaded back into the TND, or the request is detoured to a corresponding buffer. By deriving an analytical model, the performance penalty and hardware overhead of the CMAT architecture are shown to be very small.>

A functional testing method called polynomial testing is proposed to test packet-switching networks (PSNs) used in multiprocessor systems. Focus is on applying the method to packet-switching multistage interconnection networks (PMINs). A multiple stuck-at (MSA) fault model is developed and faults are diagnosed at two different levels: network level and switch level. The former uses each processor as a tester and can test part of the network concurrently with the normal operations on the remaining part of the network; the latter uses switches in the network as testers and is inherently an autonomous testing method. To facilitate the network-level testing, the routing dynamic in a PMIN is eliminated by synchronizing switch operations. The network is then decomposed into routes, each of which is tested after transforming it into a polynomial calculator. For switch-level testing, a built-in tester (BIT) is embedded into each switch's structure to provide self-testing capabilities. Network-level testing is distributed and suitable for concurrent testing, whereas switch-level testing is done offline, and needs only a small testing time.>

A cost-effective design is proposed for circuit-switching multistage interconnection networks (CSMINs). Increase of the network bandwidth and reduction of the network size (and thus low costs) are accomplished by network overlapping and memory interleaving (NOMI), instead of by increasing the number of switches or adding buffers. NOMI and its control principle are described on the basis of the structure and interconnection functions of CSMINs. Detailed accounts of both the network design and the drastic reduction in hardware costs are given. The impact of NOMI on system performance is also analyzed.