bluuebunny/crossref_metadata_2025 huggingface dataset:
Fast Parallel Multiplication Using Redundant Quarternary Number System
Authors: De Mallika , Sinha Bhabani P.
Published: October 2003

In this paper, we propose a high-speed VLSI multiplication scheme using redundant radix-4 representation of numbers. For m-digit by m-digit redundant radix-4 integer multiplication, we first generate m partial products, each of (m+1) digits in redundant radix-4 (RR-4) number system. These partial products are then added up four at a time by means of redundant quarternary adders. Parallel addition of four (m+1)-digit redundant radix-4 numbers can be performed in a constant time independent of m without any carry propagation. With these adders, multiplication of two m-digit numbers in RR-4 number system can be performed in ⌈(1/2)log2 m ⌉ + 1 steps of such additions of four RR-4 numbers. The number of computational elements of an m-digit multiplier based on the proposed algorithm is O(m2). Since the multiplier has a regular cellular array structure, it is suitable for VLSI implementation with O(m2 log m) AT-value.
Simple and Work-Efficient Parallel Algorithms for the Minimum Spanning Tree Problem
Authors: Zaroliagis Christos D.
Published: October 2003

Two Simple and work-efficient parallel algorithms for the minimum spanning tree problem are presented. Both algorithms perform O(m log n) work. The first algorithm runs in O( log 2 n) time on an EREW PRAM, while the second algorithm runs in O( log n) time on a COMMON CRCW PRAM.
On the Hardness of Devising Interval Routing Schemes
Authors: Flammini Michele
Published: October 2003

The k-Interval Routing Scheme (k-IRS) is a compact routing scheme on general networks. It has been studied extensively and recently been implemented on the latest generation of the INMOS transputer router chips. In this paper we investigate the time complexity of devising a minimal space k-IRS and we prove that the problem of deciding whether there exists a 2-IRS for any network G is NP-complete. This is the first hardness result for k-IRS where k is constant and the graph underlying the network is unweighted. Moreover, the NP-completeness holds also for linear and strict 2-IRS.
On Embedding Cycles in k-Ary n-Cubes
Authors: Ashir Yaagoub A. , Stewart Iain A.
Published: October 2003

We completely classify when a k-ary n-cube [Formula: see text], for k ≥ 3 and n ≥ 2, contains a cycle of some given length. Our analysis yields an efficient algorithm for generating a cycle of any given length, if indeed one exists, thus answering a question posed by Bose, Broeg, Kwon and Ashir.
Fault-Tolerant Parallel Communication in the Star Network
Authors: Rescigno A. A.
Published: October 2003

In this paper we study the problem of fault-tolerant parallel routing in the star network, i.e., we assume that all processors send packets according to the prescribed protocol but some packets may fail to reach (on time) their destination. Using the Information Dispersal Algorithm (IDA) we obtain a fault-tolerant randomised routing algorithm whose probability of success is 1 - N-Θ(n), where N = n! is the number of nodes of the star graph Sn.
Efficient Byzantine Agreement in Networks with Random Faults
Authors: Malinowski Adam
Published: October 2003

We consider the Byzantine Agreement problem under the assumption that nodes and links of a synchronous network fail independently with constant probabilities p < 1/3 and q< 1 - 1/2(1-p), respectively. In a unit of time any node can send or receive a single bit of information. We present an asymptotically time-optimal agreement protocol, whose probability of correctness exceeds 1 - n-∊, where n is the number of nodes and ∊ > 0 an arbitrary constant.
Reliability Evaluation of Braided Networks Using A Recursive Method
Authors: Latifi Shahram , Gajjala Ramesh
Published: October 2003

The global reliability of a connected network reflects the probability of having a connected path between every pair of processors. Given any network, there are several ways of finding this reliability measure such as path set and cut set methods. These methods are computation extensive for large networks and do not utilize the symmetry of the networks. In this paper, we present a generalization of a special class of networks called Braided-Line networks and derive the reliability expressions for these networks using recursive techniques. These recursive techniques utilize the symmetry of the networks thus reducing the computation time of the global reliability substantially.
Competitive Dynamic Multiprocessor Allocation for Parallel Applications
Authors: Brecht Timothy , Deng Xiaotie , Gu Nian
Published: October 2003

We study dynamic multiprocessor allocation policies for parallel jobs, which allow the preemption and reallocation of processors to take place at any time. The objective is to minimize the completion time of the last job to finish executing (the makespan).

We characterize a parallel job using two parameter. The job's parallelism, Pi, which is the number of tasks being executed in parallel by a job, and its execution time, li, when Pi processors are allocated to the job. The only information available to the scheduler is the parallelism of jobs. The job execution time is not known to the scheduler until the job's execution is completed. We apply the approach of competitive analysis to compare preemptive scheduling policies, and are interested in determining which policy achieves the best competitive ratio (i.e., is within the smallest constant factor of optimal).

We devise an optimal competitive scheduling policy for scheduling two parallel jobs on P processors. Then, we apply the method to schedule N parallel jobs on P processors. Finally we extend our work to incorporate jobs for which the number of parallel tasks changes during execution (i.e., jobs with multiple phases of parallelism).
Towards the Automatic Verification of Atomic Memory Protocols
Authors: Bodeveix J.-P. , Filali M.
Published: October 2003

We study the validation of implementation models of memory consistency protocols. Memory consistency protocols are modeled as transition systems and we use the methodology of refinements to validate a model against a specification. To automate the proof of such refinements, we propose a syntactic extension to the S1S decidable logic.
Array Dataflow Analysis for Explicitly Parallel Programs
Authors: Collard Jean-Fançois , Griebl Martin
Published: October 2003

This paper describes a dataflow analysis of array data structures for data-parallel and/or control- (or task-) parallel imperative languages. This analysis departs from previous work because it 1) simultaneously handles both parallel programming paradigms, and 2) does not rely on the usual iterative solving process of a set of data flow equations but extends array dataflow analysis based on integer linear programming, thus improving the precision of results.
Parallelizing Nested Loops with Approximation of Distance Vectors: A Survey
Authors: Darte Alain , Vivien Frédéric
Published: October 2003

In this paper, we compare three nested loops parallelization algorithms (Allen and Kennedy's algorithm, Wolf and Lam's algorithm and Darte and Vivien's algorithm) that use different representations of distance vectors as input. We study the optimality of each with respect to the dependence analysis it uses. We propose well-chosen examples that illustrate the power and limitations of the three algorithms. This study identifies which algorithm is the most suitable for a given representation of distance vectors.
Static Analysis to Reduce Synchronization Costs Data-Parallel Programs with Remote Memory Copy
Authors: Gupta Manish , Schonberg Edith
Published: October 2003

For a program with sufficient parallelism, reducing synchronization costs is an important objective for achieving efficient execution. This paper presents a novel methodology for reducing synchronization costs of programs compiled for SPMD execution. This methodology combines data flow analyisis with communication analysis to determine the ordering between production and consumption of data on different processors, which helps in identifying redundant synchronization. The resulting framework is more powerful than any that have been previously presented, as it provides the first algorithm that can eliminate synchronization messages even from computations that need communication. We show that several commonly occuring computation patterns such as reductions and stencil computations with reciprocal producer-consumer relationship between processors lend themselves well to this optimization, an observation that is confirmed by an examination of some HPE benchmark programs. Our framework also recognizes situations where the synchronization needs for multiple data transfers can be satisfied by a single synchronization message. This analysis, while applicable to all shared memory machines as well, is especially useful for those with a flexible cache-coherence protocol, as it identifies efficient ways of moving data directly from producers to consumers, often without any extra synchronization.
On Optimizing a Class of Multi-Dimensional Loops with Reduction for Parallel Execution
Authors: Chi-Chung Lam , Sadayappan P. , Wenger Rephael
Published: October 2003

This paper addresses the compile-time optimization of a form of nested-loop computation that is motivated by a computational physics application. The computations involve multi-dimensional surface and volume integrals where the integrand is a product of a number of array terms. Besides the issue of optimal distribution of the arrays among the processors, there is also scope for reordering of the operations using the commutativity and associativity properties of addition and multiplication, and the application of the distributive law to significantly reduce the number of operations executed. A formalization of the operation minimization problem and proof of its NP-completeness is provided. A pruning search strategy for determination of an optimal form is developed. An analysis of the communication requirements and a polynomial-time algorithm for determination of optimal distribution of the arrays are also provided.
Modular Mappings and Data Distribution Independent Computations
Authors: Hyuk-Jae Lee , Fortes José A.B.
Published: October 2003

This paper considers the problem of writing data distribution independent (DDI) programs in order to eliminate or reduce initial data redistribution overheads for distributed memory parallel computers. The functionality and execution time of DDI programs are independent of initial data distributions. Modular mappings, which can be used to derive many equally optimal and functionally equivalent programs, are briefly reviewed. Relations between modular mappings and input data distributions are then established. These relations are the basis of a systematic approach to the derivation of DDI programs which is illustrated for matrix-matrix multiplication (c = a × b). Conditions of data distributions for which it is possible to find a modular mapping that yields a programa as efficient as Cannon's algorithm are: (1) the first row of the inverse of pattern distribution of array 'a' should be equal to be equal to the second row of the inverse of pattern distribution of array 'b', (2) the second row of the inverse of pattern distribution of array 'a' should be linearly independent of the first row of the inverse of pattern distribution of array 'b', and (3) each pattern distribution of arrays 'a', 'b', and 'c' should have at least one zero entry, respectively.
On Manipulating Z-Polyhedra Using a Canonical Representation
Authors: Quinton Patrice , Rajopadhye Sanjay , Risset Tanguy
Published: October 2003

Z-polyhedra are intersections of polyhedra and integral lattices. They arise in the domain of automatic parallelization and VLSI array synthesis. In this paper, we address the problem of computation on Z-polyhedra. We introduce a canonical representation for Z-polyhedra which allows one to perform comparisons and transformations of Z-polyhedra with the help of a computational kernel on polyhedra.
Communication Generation for Block-Cyclic Distributions
Authors: Venkatachar A. , Ramanujam J. , Thirumalai A.
Published: October 2003

Data-parallel languages such as High Performance Fortran, Vienna Fortran and Fortran D include directives such as alignment and distribution that describe how data and computation are mapped onto the processors in a distributed-memory multiprocessor. A compiler for HPF that generates code for each processor has to compute the sequence of local memory addresses accessed by each processor and the sequence of send and receives for a given processor to access non-local data. In this paper, we present a novel approach for the generation of communication sets that exploits a pttern of send-receive index pairs. In addition, we present an algorithm for code generation. Experimental results demonstrate the viability of this technique.
Memory Reuse Analysis in the Polyhedral Model
Authors: Wilde D. , Rajopadhye S.
Published: October 2003

In the context of developing a compiler for a ALPHA, a functional data-parallel language based on systems of affine recurrence equations (SAREs), we address the problem of transforming scheduled single-assignment code to multiple assignment code. We show how the polyhedral model allows us to statically compute the lifetimes of program variables, and thus enables us to derive necessary and sufficient conditions for reusing memory.
Deterministic Routing on the Array with Reconfigurable Optimal Buses
Authors: Rajasekaran Sanguthevar , Sahni Sartaj
Published: October 2003

In this paper we present efficient deterministic algorithms for various classes of routing problems on the array with reconfigurable optical buses (AROB).
Routing Permutations on a 2D Grid with One-Way Edges
Authors: Panaite Petrişor
Published: October 2003

We deal with the permutation routing problem on the m × n grid with one-register vertices and one-way edges. We give a routing algrithm of O(m + n) steps which is local, that is, the routing decision of every vertex depends on the states of vertices O(1) apart. Previous work investigated either local routings on two-way edges or non local routings on one-way edges.
A Routing Strategy for Object-Oriented Applications in Massively Parallel Architectures
Authors: Boari Maurelio , Corradi Antonioo , Stefanelli Cesare , Leonardi Letizia
Published: October 2003

Parallel object-oriented environments have a high degree of dynamicity and need specialised support to achieve efficiency of execution. Static strategies are not suitable for these environments: any prediction before execution can only roughly estimate the real behaviour. In object-oriented environments, the decision to create/destroy objects is usually taken at run-time and object allocation can change during the execution. The requirement of dynamicity should be considered in the design of every component of the support. The routing system, for instance, must ensure delivery even in case of object dynamic allocation/reallocation.

The paper argues that routing algorithms for parallel object-oriented environments in massively parallel architectures should be both adaptive and efficient. We adopted a routing strategy designed to be effective in case of objects dynamically created/destroyed and capable of moving during the execution. Our adaptive strategy does not assume any knowlegde of both object allocation and system topology configuration.
Pure Greedy Hot-Potato in the 2-D Mesh with Random Destinations
Authors: Spirakis Paul , Triantafillou Vassilis
Published: October 2003

We analyze here a pure greedy hot-potato routing strategy on a two-dimensional mesh of n2 nodes. We specifically study the case of n2 packets, originating one per node, to be delivered at random uniform destinations. Each packet attempts to follow the shortest path leading first to the destination row/column (whichever is closest) and then to the actual destination node. A deflection policy ia adopted to solve conflicts. We prove that all packets are delivered to the destinations in average time O(nlogn). The average is taken over all possible destination functions. No average case analysis of pure greedy hot-potato routing was known up to now.
A Permutation Routing Algorithm for Double Loop Networks
Authors: Hwang F. K. , Lin Tzai-Shunne , Jan Rong-Hong
Published: October 2003

Double-loop networks are popular architectures for interconnecting networks. We show that these networks have parallel processing capability by giving the first permutation routing algorithm. Furthermore, we show that the number of routing steps required is equal to the diameter of the network, the best bound one can get.
Parallel Algorithms for Single-Layer Channel Routing
Authors: Greenberg Ronald I. , Hung Shih-Chuan , Shih Jau-Der
Published: October 2003

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that are known to have linear-time sequential solutions rather than limiting attention to the "river-routing" context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O( lg N) time on a CREW PRAM or [Formula: see text] time on a (common) CRCW PRAM, both with optimal work (processor-time product) of O(N), where $N$ is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of the channel contains single-sided nets. For the optimal offset problem with single-sided nets on one side of the channel, we obtain time O( lg N lg lg N) on a CREW PRAM or [Formula: see text] time on a CRCW PRAM with O(N lg lg N) work. Not only does this improve on previous results for river routing, but we can obtain an even better time of O(( lg lg N)2) on the CRCW PRAM in the river routing context. In addition, wherever our results allow a channel boundary to contain single-sided nets, the results also apply when that boundary is ragged and N incorporates the number of bendpoints.
Arbitrary Size Benes Networks
Authors: Chang Chihming , Melhem Rami
Published: October 2003

The Benes network is a rearrangeable nonblocking network which can realize any arbitrary permutation. Overlall, the r-dimensional Benes network connects 2r inputs to 2r outputs through 2r - 1 levels of 2 × 2 switches. Each level of switches consists of 2r - 1 switches, and hence the size of the network has to be a power of two. In this paper, we extend Benes networks to arbitrary sizes. We also show that the looping routing algorithm used in Benes networks can be slightly modified and applied to arbitrary size Benes networks.
Ring Embedding in Hypercubes with Faculty Nodes
Authors: Kim Jin S. , Maeng Seung Ryoul , Yoon H.
Published: October 2003

Hypercube is an attractive structure for parellel processing due to its symmetry and regularity. To increase the reliability of hypercube based systems and to allow their use in the presence of faulty nodes, efficient fault-tolerant schemes in hypercubes are necessary. In this paper, we present an algorithm for embedding rings in hypercubes based multiprocessor network in the event of node failures. The algorithm can tolerate up to θ(2n/2) faults, and guarantee that given any f < (n - 2k)2k faulty nodes, it can find a ring of size at least 2n - 2f for k = 0 and 2n - 2k f - 22k for k ≥ 1 in an n-dimensional hypercube. It improves over existing algorithms in the size of ring.
Dictionary Compression on the Pram
Authors: Hirschberg Daniel S. , Stauffer Lynn M.
Published: October 2003

Parallel algorithms for lossless data compression via dictionary compression using optimal, longest fragment first (LFF), and greedy parsing strategies are described. Dictionary compression removes redundancy by replacing substrings of the input by references to strings stored in a dictionary. Given a static dictionary stored as a suffix tree, we present a CREW PRAM algorithm for optimal compression which runs in O(M + log M log n) time with O(nM2) processors, where it is assumed that M is the maximum length of any dictionary entry. Under the same model, we give an algorithm for LFF compression which runs in O( log 2 n) time with O(n/ log n) processors where it is assumed that the maximum dictionary entry is of length O( log n). We also describe an O(M + log n) time and O(n) processor algorithm for greedy parsing given a static or sliding-window dictionary. For sliding-window compression, a different approach finds the greedy parsing in O( log n) time using (O(nM log M/ log n) processors. Our algorithms are practical in the sense that their analysis elicits small constants.
Gradual Design of a Causal Broadcast Protocol
Authors: Badache Nadjib , Maddi Aomar
Published: October 2003

This paper presents a gradual approach to designing a protocol to implement causal ordering in the particular case of a broadcast group. Each message is received by all the processes of the group, including its sender. The protocol we obtain is simple and has low communication overhead.
On Self-Stabilizing Wait-Free Clock Synchronization
Authors: Papatriantafilou Marina , Tsigas Philippas
Published: October 2003

A protocol which can tolerate any number of processors failing by ceasing operation for unbounded time and resuming operation (with or) without knowing that they were faulty is called wait-free; if it also works correctly even when the starting state of the system is arbitrary, it is called wait-free, self-stabilizing. This work is on the problem of wait-free, self-stabilizing clock synchronization of n processors in "in-phase" multiprocessor systems and presents a protocol that achieves quadratic synchronization time, by "re-parameterizing" and improving the best previously known solution, which had cubic synchronization time. Both the protocol and its analysis are intuitive and easy to understand.
A Model-Based Concurrent Specification Language over CML: Semantic Foundations
Authors: Debbabi Maurad
Published: October 2003

In this paper we address the problem of specification and design of concurrent systems. More accurately, we present the definition of a new specification language that is formal, wide-spectrum, model-based, concurrent, polymorphic and strongly implicitly typed. The language is built upon a concurrent, funtional and imperative programming language: Concurrent ML. Specification aspects are supported thanks to the addition of some specification constructs and also by allowing axioms to ML structures and signatures. The resulting specification language is thus highly expressive though it embodies a restricted number of concepts. We present here the motivations underlying the definition of such a language as well as the design choices. Furthermore, we introduce the specification and development methology and illustrate it on various examples. We will see that many specification styles are allowed: algebraic, applicative, state-based, concurrent applicative and concurrent imperative. We show that the language rests on secure theoretical foundations exemplified by formal syntactic and semantic definitions. The latter consists in a static semantics together with a dynamic semantics. The static semantics reconstructs not only principal types but also minimal side and communication effects. This is done thanks to an extension of the type and effect discipline. The language is also endowed with a dynamic denotational semantics. The underlying model is based on an extension of the acceptance trees model to handle value-passing, communication, assignment, sequencing, return of results and higher order objects.
Demand-Driven Data Flow Analysis for Communication Optimization
Authors: Yuan Xin , Gupta Rajiv , Melhem Rami
Published: October 2003

Exhaustive global array data flow analysis for communication optimization is expensive and considered to be impractical for large programs. This paper proposes a demand-driven analysis approach that reduces the analysis cost by computing only the data flow information related to optimizations. In addition, the analysis cost of our scheme can be effectively managed by trading space for time or compromising precision for time.
Optimal and Near–Optimal Solutions for Hard Compilation Problems
Authors: Kremer Ulrich
Published: October 2003

An optimizing compiler typically uses multiple program representations at different levels of program and performance abstractions in order to be able to perform transformations that – at least in the majority of cases – will lead to an overall improvement in program performance. The complexities of the program and performance abstractions used to formulate compiler optimization problems have to match the complexities of the high–level programming model and of the underlying target system.

Scalable parallel systems typically have multi–level memory hierarchies and able to exploit coarse–grain and fine–grain parallelism. Most likely, future systems will have even deeper memory hierarchies and more granularities of parallelism. As a result, future compiler optimizations will have to use more and more complex, multi–level computation and performance models in order to keep up with the complexities of their future target systems. Most of the optimization problems encountered in highly optimizing compilers are already NP–hard, and there is little hope that most newly encountered optimization formulations will not be at least NP–hard as well.

To face this "complexity crisis", new methods are needed to evaluate the benefits of a compiler optimization formulation. A crucial step in this evaluation process is to compute the optimal solution of the formulation. Using ad–hoc methods to compute optimal solutions to NP–complete problems may be prohibitively expensive. Recent improvements in mixed integer and 0–1 integer programming suggest that this technology may provide the key to efficient, optimal and near–optimal solutions to NP–complete compiler optimization problems. In fact, early results indicate that integer programming formulations may be efficient enough to be included in not only evaluation prototypes, but in production programming environments or even production compilers. This paper discusses the potential benefits of integer programming as a tool to deal with NP–complete compiler optimization formulations in compilers and programming environments.
Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling
Authors: Darte Alain , Silber Georges-André , Vivien Frédéric
Published: October 2003

Tiling is a technique used for exploiting medium-grain parallelism in nested loops. It relies on a first step that detects sets of permutable nested loops. All algorithms developed so far consider the statements of the loop body as a single block, in other words, they are not able to take advantage of the structure of dependences between different statements. In this paper, we overcame this limitation by showing how the structure of the reduced dependence graph can be taken into account for detecting more permutable loops. Our method combines graph retiming techniques and graph scheduling techniques. It can be viewed as an extension of Wolf and Lam's algorithm to the case of loops with multiple statements. Loan independent dependences play a particular role in our study, and we show how the way we handle them can be useful for fine-grain loop parallelization as well.
Compile-Time Cache Performance Prediction and Its Application to Tiling
Authors: Kaplow Wesley K. , Szymanski Boleslaw K.
Published: October 2003

Tiling has been used by parallelizing compilers to define fine-grain parallel tasks and to optimize cache performance. In this paper we present a novel compile-time technique, called miss-driven cache simulation, for determining loop tile sizes that achieve the highest cache hit-rate. The widening disparity between a processor's peak instruction rate and main memory access time in modern computer systems makes this kind of optimization increasingly important for overall program efficiency.

Our simulation technique generates only those references of a loop nest that may generate a cache memory miss and processes them on an architecturally accurate cache model at compile-time. Processing only a small portion of the memory reference trace of a program yields simulation speeds in the millions of memory references per second on workstations, with statistics of misses per reference and inter-reference interference counts gathered at the same time. These simulation speeds and statistics allow for the accurate analysis of the impact of cache optimizations at compile-time.

We discuss the results of applying this method to guide loop tiling for such commonly used computational kernels as matrix multiplication and Jacobi iteration for various cache parameters.
On Tiling as a Loop Transformation
Authors: Xue Jingling
Published: October 2003

This paper is a follow-up Irigoin and Triolet's earlier work and our recent work on tiling. In this paper, tiling is discussed in terms of its effects on the dependences between tiles, the dependences within a tile and the required dependence test for legality. A necessary and sufficient condition is given for enforcing the data dependences of the program, while Irigion and Triolet's atomic tile constraint is only sufficient. A condition is identified under which both Irigoin and Triolet's and our constraints are equivalent. The results of this paper are discussed in terms of their impact on dependence abstractions suitable for legality test and on tiling to optimise a certain given goal.
Compiling for Scalable Multiprocessors with Polaris
Authors: Paek Yunheung , Padua David A.
Published: October 2003

Due to the complexity of programming scalable multiprocessors with physically distributed memories, it is onerous to manually generate parallel code for these machines. As a consequense, there has been much research on the development of compiler techniques to simplify programming, to increase reliability, and to reduce development costs. For code generation, a compiler applies a number of transformations in areas such as data privatization, data copying and replication, synchronization, and data and work distribution. In this paper, we discuss our recent work on the development and implementation of a few compiler techniques for some of these transformations. We use Polaris, a parallelizing Fortran restructurer developed at Illinois, as the infrastructure to implement our algorithms. The paper includes experimental results obtained by applying our techniques to several benchmark codes.
High Performance Fortran, Version 2
Authors: Schreiber Robert
Published: October 2003

This paper introduces the ideas that underly the data-parallel language High Performance Fortran (HPF) and the new ideas in version 2 of HPF. It first reviews HPF's key language elements. It discusses the meaning of data parallelism and the limitations of HPF version 1 as a data-parallel programming language.

The second part of the paper is a review of the development of version 2 of HPF. The extended language, under development in 1996, includes a richer data mapping capability; an extension to the independent loop that allows reduction operations in the loop range; a means for directing the mapping of computation as well as data; and a way to specify concurrent execution of several parallel tasks on disjoint subsets of processors.
Effects of In Vitro and In Vivo Qi-therapy on Neutrophil Superoxide Generation in Healthy Male Subjects
Authors: Lee Myeong Soo , Jeong Seong Min , Jang Hye-Sook , Ryu Hoon , Moon Sun-Rock
Published: October 2003

The present study investigated the effects of in vitro and in vivo Korean ChunSoo Qi-Energy Healing on neutrophil superoxide generation. Neutrophil superoxide generation was measured by a chemiluminescence assay. Superoxide generation was significantly increased in vitro by emitted Qi-therapy (QT) of 60-second duration and 150-second duration compared to control (1.59-fold for 60 seconds, p < 0.05; 1.50-fold for 150 seconds, p < 0.05). Neutrophil superoxide generation increased significantly immediately after 5 minutes of QT in vivo (1.42-fold, p < 0.05). These results show that QT in vivo and in vitro has an acute stimulatory effect on neutrophil superoxide generation. This study provides direct scientific support that Qi as such may positively affect human innate immunity.
Role of Component Herbs in Antioxidant Activity of Shengmai San — A Traditional Chinese Medicine Formula Preventing Cerebral Oxidative Damage in Rat
Authors: Ichikawa Haruyo , Wang Xuejiang , Konishi Tetsuya
Published: October 2003

Traditional Chinese medicine (TCM) is an attractive model for studying antioxidant-based composite therapy. We previously reported that Shengmai San (SMS), a TCM formulation for treating cardiac disorders, inhibited cerebral oxidative damage in rats when evaluated by both glutathione peroxidase (GPX) activity loss and thiobarbituric acid reactive substance (TBARS) formation after forebrain ischemia-reperfusion. In the present study, we further examined the preventive effect of SMS and related decoctions composed of three component herbs (Panax ginseng, Ophiopogon japonicus and Schisandra chinensis) against oxidative brain injury to rationalize the complex formulation of SMS. Schisandra chinensis itself and decoctions containing it all inhibited TBARS formation in vivo. In contrast, Ophiopogon japonicus itself and formulations containing it had little effect on TBARS formation. GPX activity loss in vivo, on the other hand, was completely prevented only by SMS and Ophiopogon japonicus itself. A comparison of the in vitro antioxidant potential of SMS and related decoctions and in vivo effectiveness in preventing cerebral oxidative damage revealed that all the in vitro antioxidant indices examined here essentially correlated well with inhibition of TBARS formation in vivo. DPPH quenching and crocin bleaching activities showed particularly good correlation, and then, superoxide scavenging activity followed. However, none of them correlated with the inhibition of GPX activity loss in vivo. The role of each component herb is also discussed for the SMS effect.
Antioxidative and Antimutagenic Activities of Healthy Herbal Drinks from Chinese Medicinal Herbs
Authors: Chen Wenlung , Weng Yih-Ming , Tseng Chin-Yin
Published: October 2003

Twenty-nine Chinese medicinal herbs and three healthy herbal drinks made of those herbs in a food processing pilot plant were tested for their antioxidative, free radical scavenging, mutagenic and antimutagenic activities. Water extracts of herbs (with few exceptions) and herbal drinks showed free radical scavenging activity. All water extracts of herbs and herbal drinks showed no mutagenicity toward Salmonella typhimurium tester strains TA98 and TA100 used in the Ames mutagenic tests. In the antimutagenic tests, the mutagenic activity of 4-nitroquinoline N-oxide (NQNO) toward S. typhimurium TA98 was markedly inhibited by water extracts of herbs and herbal drinks. Based on the results, it is suggested that the herbal drinks manufactured in pilot-plant scale are safe and can be served as health-promoting drinks for the public.
Induction of Apoptosis in HL-60 Cells Treated with Medicinal Herbs
Authors: Nishida S. , Kikuichi S. , Yoshioka S. , Tsubaki M. , Fujii Y. , Matsuda H. , Kubo M. , Irimajiri K.
Published: October 2003

In order to develop a new apoptosis inducer, we screened 22 crude drugs for their apoptosis-inducing activity. It was found that Glycyrrhiza uralensis, Cynomorium songaricum, Eucommia ulmoides, Phellodendron amurense, Cinnamomum cassia and Paeonia lactiflora induced the death of HL-60 cells. To investigate the mechanism of apoptosis induced by these six crude drugs, the mitochondrial transmembrane potential and the activity of caspase-3 were measured. Reduced mitochondrial transmembrane potentials within 12 hours after the administration of Glycyrrhiza uralensis, Cynomorium songaricum, Phellodendron amurense and Paeonia lactiflora, and within 24 hours after the administration of Eucommia ulmoides and Cinnamomum cassia were observed. All of the six apoptosis-inducing crude drugs increased caspase-3 activity within 12–36 hours after administration. After further examining the apoptosis-inducing activity of berberine, palmatine, panelofuroline and glycyrrhizin, which were the ingredients obtained from Phellodendron amurense, Glycyrrhiza uralensis and Paeonia lactiflora, it was found that only berberine could induce apoptosis. From these results, it was concluded that the apoptosis induced by the six crude drugs (Glycyrrhiza uralensis, Cynomorium songaricum, Eucommia ulmoides, Phellodendron amurense, Cinnamomum cassia and Paeonia lactiflora) occurred via the mitochondrial route and that the apoptosis-conducting mechanism acted through a cascade involving caspase-3.
Effects of Shao-Fu-Zhu-Yu-Tang on Motility of Human Sperm
Authors: Yang Ching-Chiang , Chen Jung-Chou , Chen Guang-Wei , Chen Yi-Shuan , Chung J.G.
Published: October 2003

Shao-Fu-Zhu-Yu-Tang (SFZYT) is reportedly beneficial to sperm. In this study, we examined sperm acrosomal activity and serum free radical changes to evaluate the possible mechanism of SFZYT. A clinical study evaluated the sperm count and motility in 36 patients with chronic prostatitis before and after treatment for 60 days. The results revealed a significant increase in sperm motility after treatment as evaluated by computer-assisted semen analysis (17.27 ± 9.00 versus 28.29 ± 10.00, p < 0.01). An increase in sperm quantity and quality was observed by count and morphology with a high-powered intravital microscope. To gain an understanding of the mechanisms that caused this effect, we assessed sperm acrosin activity levels before (10.6 μ lu /106) and after medication (28.6 μ lu /106)( p < 0.01). The levels of the free radicals was relatively higher before medication, 2144, compared to a normal value of 780 after medication ( p < 0.01). In conclusion, SFZYT increased the motility and quality of human semen and this increase is related to an increase in sperm acrosin activity. SFZYT also works as a sperm antioxidant and antiaging agent.
Acupuncture Modulates Expressions of Nitric Oxide Synthase and c-Fos in Hippocampus After Transient Global Ischemia in Gerbils
Authors: Kang Ji-Eun , Lee Hye-Jung , Lim Sabina , Kim Ee-Hwa , Lee Tae-Hee , Jang Mi-Hyeon , Shin Min-Chul , Lim Baek-Vin , Kim Youn-Jung , Kim Chang-Ju
Published: October 2003

The effects of acupuncture on the expressions of nitric oxide synthase (NOS) and c-Fos in the hippocampus of gerbils after transient ischemia were investigated via nicotinamide adenine dinucleotide phosphate-diaphorase (NADPH-d) histochemistry and Fos immunohistochemistry. In animals of the ischemia-induction groups, both common carotid arteries were occluded for 5 minutes. Animals of the acupunctued groups were given acupunctural treatment at Zusanli twice daily for 9 consecutive days. Acupuncture was shown to decrease NADPH-d and c-Fos levels in both the sham-operation group and the ischemia-induction group. These results suggest that acupuncture modulates the expressions of NOS and c-Fos in the hippocampus.
Effect of Moxibustion Stimulation of Various Skin Areas on Cortical Cerebral Blood Flow in Anesthetized Rats
Authors: Uchida Sae , Suzuki Atsuko , Kagitani Fusako , Nakajima Kaori , Aikawa Yoshihiro
Published: October 2003

The effect of moxibustion stimulation of various skin areas (cheek, forepaw, upper arm, chest, back, lower leg, hindpaw and perineum) on cerebral blood flow (CBF) of the parietal cortex was examined in anesthetized rats after eliminating emotional influences. Moxibustion stimulation was performed by burning a moxa cone of about 4 mg weight placed on the shaved skin. CBF of the parietal cortex was measured using a laser Doppler flowmeter. Stimulation of the cheek, forepaw, upper arm and hindpaw produced significant increases in CBF, but stimulation of the other areas did not produce significant responses. Moxibustion stimulation of the forepaw and hindpaw produced an increase in the mean arterial pressure (MAP), while stimulation of the other areas did not. After spinal transection at the 2nd thoracic level, the MAP response to stimulation of the forepaw was abolished, whereas the CBF response to stimulation of the forepaw remained. The CBF response in spinalized rats was not affected by cutting cervical sympathetic and facial parasympathetic nerves, while it was almost abolished by intravenous administration of muscarinic and nicotinic cholinergic blocking agents. The CBF response was abolished by crushing the brachial plexus ipsilateral to the stimulated side. It is suggested that the increase in CBF, independent of MAP and emotional responses, elicited by moxibustion stimulation is a reflex response whose afferent pathway is composed of somatic afferent nerves, and whose efferent pathway involves intracerebral cholinergic nerves. A contribution of endogenous opioids in the present CBF responses was neglected, because naloxone did not influence the CBF responses.
Challenge Tests and Kampo Medicines: Case Report and Review of the Literature
Authors: Mantani Naoki , Kogure Toshiaki , Tamura Jun'ichi , Shimada Yutaka , Terasawa Katsutoshi
Published: October 2003

In order to diagnose Kampo medicine-induced liver injury, a challenge test using the suspected medicine is the most reliable method of assessing the relationship between Kampo medication and liver injury. However, such a challenge test may cause severe liver injury. We examined the clinical features and safety of challenge tests conducted by a physician in a case of Kampo medicine-induced liver injury that we encountered as well as in the previous literature (six cases) in Japan. In all cases except two, one-third of the daily dose was given a few times for the challenge test (challenge dose was not described in two cases). The reaction induced by the challenge peaked 1–3 days after challenge. Mild eosinophilia (6%) was observed in two cases. All liver injuries induced by challenge cleared within 2 weeks, and neither severe nor fatal liver injury was observed. In conclusion, a challenge with a small dose of Kampo medicine conducted in our case and in the previous literature induced mild and reversible liver injury. The safety and availability of challenge with a small dose of Kampo medicine should be further examined in a larger population with Kampo medicine-induced liver injury.
Effects of Aqueous Extract of Sophora flavescens on the Expression of Cell Cycle Regulatory Proteins in Human Oral Mucosal Fibroblasts
Authors: Kim Hyun-A , You Hyung-Keun , Shin Hyung-Shik , Kim Youn-Chul , Kang Tai-Hyun , Yu Hyeon-Hee , You Yong-Ouk
Published: October 2003

Sophorae Radix, the dried roots of Sophora flavescens AITON (Leguminosae), has been used in Oriental traditional medicine for treatment of skin and mucosal ulcers, sores, gastrointestinal hemorrhage, diarrhea, inflammation and arrhythmia. In the present study, we examine the effect of the aqueous extract of Sophorae Radix (AESR) on cell proliferation and cell cycle regulation in human oral mucosal fibroblasts (HOMFs). To study the molecular mechanisms of cell cycle regulation by AESR, we also measured the intracellular levels of cell cycle regulatory proteins such as cyclin D, cyclin-dependent kinases (CDK)-4, CDK-6, cyclin E, CDK-2, p53, p21WAF1/CIP1 and p16INK4 . Cell proliferation was increased in the presence of 10~500 μg/ml of AESR. Maximal growth stimulation was observed in those cells exposed to 100 μg/ml of AESR. Exposure of HOMFs to 100 μg/ml of AESR resulted in an increase of cell cycle progression. The levels of cyclin E and CDK-2 were increased in HOMFs after 100 μg/ml of AESR treatment, but the levels of cyclin D, CDK-4, and CDK-6 were unchanged. After exposure to 100 μg/ml of AESR, the protein levels of p16INK4A and p53 were decreased as compared to that of the control group, but the level of p21WAF1/CIP1 was similar in the cells treated with 100 μg/ml of AESR and untreated cells. The results suggest that AESR may increase cell proliferation and cell cycle progression in HOMFs, which is linked to increased cellular levels of cyclin E and CDK-2 and decreased cellular levels of p53 and p16INK4A . Further studies are necessary to clarify the active constituents of AESR responsible for such biomolecular activities.
EEG Alpha Blocking Correlated with Perception of Inner Light During Zen Meditation
Authors: Lo Pei-Chen , Huang Ming-Liang , Chang Kang-Ming
Published: October 2003

According to the experimental results and practitioners' subjective experience, we report some hypotheses that may account for meditative phenomena during the practice of Zen-Buddhism. Orthodox Zen-Buddhist practitioners, aiming to prove the most original true-self, discover and uncover the inner energy or light on the way towards their goal. Perception of the inner light can be comprehended as resonance. Uncovering the inner energy optimizes physiological and mental health. In the meditation experiment, a significant correlation was observed between perception of the inner light and electroencephalographic (EEG) alpha blockage. We further examined this phenomenon by recording the EEG from subjects during a blessing that the subjects did not know being given. During the blessing period, significant alpha blocking was observed in experimental subjects who had been practicing meditation for years in preparation for being in resonance with the inner light. This report provides a new insight into the debate that meditation benefits our health.
Pattern of Alternative Medicine Usage Among the Chinese Breast Cancer Patients: Implication for Service Integration
Authors: Abdullah Abu S.M. , Lau Yvonne , Chow Louis W.C.
Published: October 2003

The study examined the pattern of and factors associated with use of alternative medicine (AM) among Chinese breast cancer patients. An analytical, cross-sectional survey of 352 breast cancer patients from two breast cancer centers was conducted in 1997. Amongst the respondents, the usage rate of alternative medicine was 27.8%. Factors forming the use of AM included being young to middle-aged, having higher education and a belief that AM would enhance orthodox treatment. A substantial proportion of Chinese breast cancer patients use AM besides conventional medicine. There is a need to integrate AM with conventional medicine to improve the service provision for cancer patients.
Effect of One Week Treatment with Ginkgo biloba Extract (EGb761) on Ischemia-Induced Infarct Volume in Gerbils
Authors: Chung Shu-Ying , Wang Ming-Fu , Lin Jing-Ying , Lin Ming-Cheng , Liu Hui-Ming , Cheng Fu-Chou
Published: October 2003

The present study was designed to evaluate the neuroprotective effects of Ginkgo biloba leaf extract (EGb761) in male gerbils subjected to focal cerebral ischemia produced by permanent occlusion of the right middle cerebral artery. In this study, gerbils were fed standard chow with or without EGb761 (100 mg/kg/day, i.g.) prior to cerebral ischemia for 1 week. Gerbils were anesthetized and craniectomized to expose the right middle cerebral artery (MCA). The right MCA was constricted with an 8-0 suture to produce a permanent ligation. Infarct volume was assessed by TTC (2,3,5-triphenyl-tetrazolium chloride) staining 24 hours after initiation of cerebral ischemia. Results showed that the EGb761 group had significant reduction of infarct volume 4 and 6 mm from the frontal pole by 40% and 30%, respectively when compared to the control group ( p < 0.05). Mean locomotor activity of gerbils was reduced 24 hours after the occlusion of the MCA in both groups. However, there was no difference in locomotor activity between groups either 30 minutes before or 24 hours after the occlusion ( p < 0.05).