Hadoop MapReduce is a software framework for processing vast amounts of data in parallel on large clusters. As data size increases, a need arises to resolve the significant increase in the disk I/O of reducer nodes, which may cause runtime bottlenecks. In response, we propose Bucket MapReduce, a system that utilizes bucket sort and pipeline parallelism to improve the performance of Hadoop MapReduce. Several parameters may influence the performance in Bucket MapReduce, and thus we will further discuss parameter tuning. In this paper, we perform experiments on TeraSort benchmark. Bucket MapReduce successfully reduces local disk I/O by 61% and improves the runtime by 1. 39× in 800GB TeraSort benchmark.

In research, time series-based (time-aware) QoS modeling and forecasting for Web services (WSs) has been studied for over a decade, and a large number of research papers have been published; however, this current research lacks a systematic and comprehensive survey. Thus, in this article, an insightful and detailed review and investigation of current WS QoS time series modeling and forecasting research is provided. Based on our investigation of the collected literature, we identify and divide the entire research subject into four essential research concerns (components): the addressed problem, the proposed or employed approach, the considered performance measure, and the adopted QoS time series dataset. This article reviews, classifies, and discusses current studies in terms of the four identified research concerns. Moreover, for each research concern, a set of criteria and classification are proposed for its detailed categorization and comparison. Finally, this survey also discusses the insufficiency of current studies in each research concern and the potential future directions of this research area. Overall, this article can be an informative guide for researchers to understand the concerns that they should address when studying this research subject and to clearly comprehend what has been done in current research for each identified research concern.

Currently, statistical time-series methods have primarily been employed to predict time-aware dynamic quality of service (QoS) attributes for Web services. In this paper, we propose the application of genetic programming (GP) for such predictions. Our experimental results indicate that the GP-based approach is more accurate than the other approaches presented for comparison. However, for the efficient management of such attributes for cloud services, including their modeling and forecasting, the current research is insufficient because a set of research questions remains unanswered. In this paper, we first clearly define these research questions and then design and perform a set of empirical experiments to address the questions. Finally, the experimental results are exhaustively discussed to answer the studied research questions. The empirical study and analysis presented in this paper could be informative for the management (modeling and forecasting) of the time-aware dynamic QoS attributes of cloud services. For example, we verify that machine-learning approaches are generally superior to the widely used statistical time-series methods in terms of both modeling accuracy and forecasting accuracy. Furthermore, after considering a variety of situations and cases, the GP-based approach is still the best option for the studied problem. In addition, except for the technical approaches, this paper also exhaustively studies the influence of the properties of the cloud dynamic QoS attributes, including their size and time granularity.

This paper introduces a novel TV control simulation system that recognizes hand gestures and track hand joints based on Convolutional Neural Networks (CNN) and Convolutional Pose Machines (CPM). The system provides users with an intuitive means of controlling television functions through hand gestures. Moreover, based on relative position and angle of fingers, users can manipulate an onscreen cursor and continuously modify volume & channels at varying speed. We achieved 95.8 percent testing accuracy in 19 gestures with 4 subjects, and average 11 & 45 fps while conducting CPM and CNN respectively.

MapReduce, proposed as a programming model, has been widely adopted in the field of text processing over large datasets with the capability of exploiting the distributed resources and processing the large-scale data. Attributed to its simplicity and scalability, the success seems to have the potential to make Big Data processing by cloud computing available. Nevertheless, such promise is accompanied by the difficulty of fitting the applications into MapReduce. This is because MapReduce is limited to the kind of applications that every input key-value pair is independent of each other. In this paper, we extend the general applicability of MapReduce by allowing the dependence within a set of input key-value pairs but preserving independence among all sets. Such this new modeling paradigm intends MapReduce to shift processing the independent input key-value pairs to processing the independent sets. However, the advancement in the applicability brings the intricate problem of how two-stage processing structure, inherent in MapReduce, handles the dependence within a set of input key-value pairs. To tackle this problem, we propose the design pattern called two-phase data processing. It expresses the application in two phases not only to match the two-stage processing structure but to exploit the power of MapReduce through the cooperation between the mappers and reducers. In addition, we present the design methodology-multiple two-phase data processing-to offer advice on processing the independent sets. The experiment of background subtraction, a part of video surveillance, proves that the new modeling paradigm broadens the possibilities of MapReduce and demonstrates how our design methodology guides the applications to the implementation.

Dynamic binary translation (DBT) is a core technologyto many important applications such as system virtualization, dynamic binary instrumentation, and security. However, there are several factors that often impede its performance: 1) emulation overhead before translation; 2) translation and optimization overhead; and 3) translated code quality. The issues also include its retargetabilitythat supports guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs-an important feature to system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, and use a multithreaded approach to implement DBT. By running the translator and the dynamic binary optimizer on different cores with different threads, it could off-load the overhead incurred by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and Low-Level Virtual Machine (LLVM) as our building blocks, we demonstrated in a multithreaded DBT prototype, called Hybrid-QEMU (HQEMU), that it could improve QEMU performance by a factor of 2.6x and 4.1x on the SPEC CPU2006 integer and floating point benchmarks, respectively, for dynamic translation of x86 code to run on x86-64 platforms. For ARM codes to x86-64 platforms, HQEMU can gain a factor of 2.5x speedup over QEMU for the SPEC CPU2006 integer benchmarks. We also address the performance scalability issue of multithreaded applications across ISAs. We identify two major impediments to performance scalability in QEMU: 1) coarse-grained locks used to protect shared data structures, and 2) inefficient emulation of atomic instructions across ISAs. We proposed two techniques to mitigate those problems: 1) using indirect branch translation caching (IBTC) to avoid frequent accesses to locks, and 2) using lightweight memory transactions to emulate atomic instructions across ISAs. Our experimental results show that for multithread applications, HQEMU achieves 25X speedups over QEMU for the PARSEC benchmarks.

Most dynamic binary translators (DBT) and optimizers (DBO) target binary traces, i.e. frequently executed paths, as code regions to be translated and optimized. Code region formation is the most important first step in all DBTs and DBOs. The quality of the dynamically formed code regions determines the extent and the types of optimization opportunities that can be exposed to DBTs and DBOs, and thus, determines the ultimate quality of the final optimized code. The Next-Executing-Tail (NET) trace formation method used in HP Dynamo is an early example of such techniques. Many existing trace formation schemes are variants of NET. They work very well for most binary traces, but they also suffer a major problem: the formed traces may contain a large number of early exits that could be branched out during the execution. If this happens frequently, the program execution will spend more time in the slow binary interpreter or in the unoptimized code regions than in the optimized traces in code cache. The benefit of the trace optimization is thus lost. Traces/regions with frequently taken early-exits are called delinquent traces/regions. Our empirical study shows that at least 8 of the 12 SPEC CPU2006 integer benchmarks have delinquent traces.

Dynamic binary translation (DBT) is a core technology to many important applications such as system virtualization, dynamic binary instrumentation and security. However, there are several factors that often impede its performance: (1) emulation overhead before translation; (2) translation and optimization overhead, and (3) translated code quality. On the dynamic binary translator itself, the issues also include its retargetability to support guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs, an important feature for system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, using multithreaded approach to implement DBT. By running the translators and the dynamic binary optimizers on different threads on different cores, it could off-load the overhead caused by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as the support of its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and LLVM (Low Level Virtual Machine) as our building blocks, we demonstrated in a multi-threaded DBT prototype, called HQEMU, that it could improve QEMU performance by a factor of 2.4X and 4X on the SPEC 2006 integer and floating point benchmarks for x86 to x86-64 emulations, respectively, i.e. it is only 2.5X and 2.1X slower than native execution of the same benchmarks on x86-64, as opposed to 6X and 8.4X slowdown on QEMU. For ARM to x86-64 emulation, HQEMU could gain a factor of 2.4X speedup over QEMU for the SPEC 2006 integer benchmarks.

In this paper, we present a distributed file system with storage QoS provision for cloud computing. The objective is to maximize the aggregated disk bandwidth utilization with the assurance of allocated disk bandwidth for each data transfer. First, we implement a distributed file system based on the ECNP model, which avoids matchmaker overloading and the lack of up-to-date information in the original matchmaking model. Next, resource selection policies for resource management are investigated to improve bandwidth utilization. Furthermore, we propose several dynamic replication strategies to balance the workload of resource providers. Experiments are conducted in real systems to study the performance on storage QoS with different resource selection policies and dynamic replication strategies.

The demand for huge storage space on data-intensive applications and high-performance scientific computing continues to grow. To integrate massive distributed storage resources for providing huge storage space is an important and challenging issue in Cloud and Grid computing. In this paper, we propose a distributed file system, called ASDF, to meet the demands of not only data-intensive applications but also end users, developers and administrators. While sharing many of the same goals as previous distributed file systems such as scalability, reliability, and performance, it is also designed with the emphasis on compatibility, extensibility and autonomy. With the design goals in minds, we address several issues and present our design by adopting peer-to-peer technology, replication, multi-source data transfer, metadata caching and service-oriented architecture. The experimental results show the proposed distributed file system meet our design goals and will be useful in Cloud and Grid computing.

In this paper, we present the design and implementation of a negotiation-based resource management system called Mercury. As the number of resources in Grids is increasing rapidly, selecting appropriate resources to execute tasks has become a crucial issue. The proposed system implements the Extended Contract Net Protocol (ECNP), which improves the standard bidding model by integrating a matchmaking technique. Our model addresses the issues of matchmaker overload and the lack of up-to-date resource state information in the original matchmaking model. To ensure that the system is user-friendly, we provide a web interface. By using the provided job templates, users can describe their jobs more easily, and service providers can deploy their services in the system in a simple manner. Furthermore, to improve the interoperability of the system, we adopt open standards, such as the WS-Agreement and JSDL protocols. Our experimental results demonstrate the scalability and efficiency of the system.

This paper presents an LLVM+QEMU (LnQ)framework for building high performance and retargetable binary translators with existing compiler modules. Dynamic binary translation is a just-in-time (JIT) compilation from binary code of guest ISA to binary code of host ISA. The quality of translated code is critical to the performance of a dynamic binary translator, which translates code between different IS As, so the translated code is often carefully hand-optimized. As a result, it takes tremendous implementation efforts for software engineers to port an existing dynamic binary translator to anew host ISA. The goal of LnQ framework is to enable the process of building high performance and retarget able dynamic binary translators with existing optimizers and code generation back ends. LnQ framework consists of a translation module and an emulation engine. We design the translation module based on LLVM compiler infrastructure, and use QEMU as our emulation engine. We implement an x86-to-x86 64 dynamic binary translator with our LnQ framework to show that the framework is retarget able, and conduct experiments on SPECCPU2006 benchmarks to show that the resulting binary translator has good performance. The experiment results indicate that the x86-to-x86 64 LnQ translator achieves an average speedup of 1.62X in integer benchmarks, and 3.02X in floating point benchmarks than QEMU.

In recent years, Data Grid becomes a promising technology to collect geographically distributed storage resources and provide a large amount of storage capacity. Such resources include personal computers, clusters or high-end servers managed by different administrative domains. Although many production Data Grids have been developed for various usages, there remain no approaches to integrating them together. To solve the problem, we propose a federation middleware, called FedMi, to integrate heterogeneous Data Grids as a single Data Grid and provide users with a uniform access interface. In this paper, four issues, including interoperability among Data Grids, single sign-on, secure communication and high performance data transfer, are addressed. We also present the evaluation results of the approaches proposed to improve the performance of data transfer across Data Grids.

SUMMARY In this paper, we consider the QoS‐aware replica placement problem. Although there has been much research on the problem, most approaches focus on the average system performance and ignore the quality assurance issue. However, quality assurance is crucial, especially in heterogeneous environments. To fill this research gap, we proposed four heuristic algorithms to determine the locations of replicas in order to satisfy the quality requirements imposed by data requests. Three of the algorithms are greedy heuristics called Greedy‐Cover, Cover‐Partition and Multi‐Source. The fourth algorithm is based on the Simulated Annealing technique. Our experiment results indicated that Greedy‐Cover and the Simulated Annealing‐based algorithms can find effective solutions efficiently. Copyright © 2011 John Wiley & Sons, Ltd.

In the last decade, the evolution of distributed computing has shifted from cluster computing to Grid computing. Although bidding provides a useful means of resource allocation for this novel computing paradigm, there exist two challenges to scheduling metatasks in bidding-based Grid systems. (1) The scheduling algorithm has to avert collisions between the jobs of a metatask, as well as prevent contention between the metatasks submitted by different requesters. (2) There is no global information system to facilitate optimum decision-making; hence, requesters are only aware of partial information released by resource providers. To address these challenges, we propose a set of scheduling heuristics to minimize the makespan of each metatask, while simultaneously considering the level of information about competing metatasks revealed by providers. We also present the results of experiments conducted to evaluate the performance of the proposed heuristics.

In this paper, we propose a resource management model that extends the Contract Net Protocol by integrating the advantages of the matchmaking technique. Our model addresses the issues of matchmaker overload and the lack of up-to-date resource state information suffered by the original matchmaking model. It also enables resource requesters to obtain a list of qualified resources with which they can narrow down the selection of resources and reduce the number of ineffective communication messages. In addition, we present five strategies to facilitate resource selection on our model from the perspective of turnaround time and reporton experiments to evaluate their performance. The experiment results show that, in the presence of resource contention, the probabilistic strategies outperform random and the deterministic ones, and the performance of the presented strategies executed on our model is superior to their performance on the original matchmaking model.

We study the replication transition problem (RTP) in the Grid systems. Most distributed systems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to data access pattern, and a good strategy can improve data access efficiency. However, the access pattern in a distributed system is constantly changing. As a result a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another in order to cope with the dynamic data access pattern. This paper focuses on the RTP problem for Grid systems in four communication models that have different communication capabilities, i.e., whether message forwarding is allowed and whether network capacity is uniform among different links. We show that there exists a polynomial time algorithm that provides optimal solution for the RTP problem when forwarding is not allowed and the communication links are uniform. We also propose heuristic algorithms for solving variants of the RTP problem and conduct experiments to evaluate their performances. The experimental results indicate that our proposed heuristics are very effective.

We study the replication transition problem in distributed hierarchical systems. Most distributed systems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to the data access pattern, therefore a good strategy can effectively improve data access efficiency. However, the access pattern in a distributed system is constantly changing. As a result, a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another, in order to cope with the dynamic access pattern. This paper focuses on solving the replication transition problem on tree topology, which is one of the most important models in data grid systems and Web proxy systems from the literature. To the best of our knowledge, our work is the first that proposes an optimal algorithm for the replication transition problem on tree topology. The algorithm has a time complexity of O(n log Deltalog(nLambda)), where n is the number of sites, Delta is the maximum degree in the tree and Lambda is the largest communication delay in the network.

A dynamic aspect-oriented system weaves aspects into applications at run time. As a result, a static model can be dynamically modified to include the codes needed to fulfill non-functional requirements without having to shut down the running program. Although this provides a high degree of flexibility, it may lead to a conformance problem. In this paper, we study the conformance issues of aspect-oriented programs and propose a scheme to check the conformance of running programs with the original software specification in dynamic aspect-oriented systems. First, we propose extensions of the UML model to express the specification of aspect-oriented applications, after which we study and classify typical mistakes made in deploying aspects. Then, we design a scheme to check if the current state conforms to the software specification. We take JAsCo as the target system to implement the proposed scheme. When the program starts running or aspects in the registry are changed, the system informs the developers if the current state violates the software specification.

As the number of data-intensive applications increases in various domains, scientists need to save, retrieve, and analyze increasingly large datasets. The huge volume of data and the long latency of data transfer on the Internet make it very difficult to ensure high-performance access to data grids. Thus, data replication techniques have been widely adopted to solve the latency problem. In this paper, we propose an efficient data replication algorithm for multi-source data transfer, whereby a data replica can be assembled in parallel from multiple distributed data sources and adapted to the variability of network bandwidths. The experimental results show that the proposed algorithm can obtain more aggregated bandwidth, reduce connection overheads, and achieve superior load balance.

The persistence problem of collaborative applications is an essential issue in the research of computer-supported collaborative work. A collaborative computing environment requires a simple and transparent persistence middleware to deal with complex data accesses. Therefore, in this paper, we propose a data persistence mechanism and implement a persistence server, called tree-structured persistence server (TSPS), to support the data management for collaborative applications. The TSPS allows states of collaborative applications to be stored in a tree fashion beside tables. By introducing TSPS, the problems of collaborative applications, such as persistence data access, asynchronous collaboration, latecomer, version control, etc., can be solved easily. The TSPS was originally developed to serve as a persistence layer to support a project of computer-supported collaborative work. We intend to develop our persistence mechanism for universal use so that it can be applied in more application areas.

Computer-supported cooperative work (CSCW) supports groups with communication and coordination during the execution of their activities. It allows physically dispersed teams to engage in a common task by providing an interface to a shared workspace. A variety of synchronous applications are playing a major role in distance education, joint program development, cooperative publishing, etc. These applications are usually platform-dependent, groupware programmers have to develop new applications for each groupware platform. In this paper, we present a developing environment called CollabRunJava. Users can collaborate to design and process their job and can also develop groupware only concentrate on application-specific details on our system. CollabRunJava supports 2 modes for developing applications. In the instant-develop mode, user can immediately execute and test the classes. In the runtime-evolution mode, user can observe application behavior, debug applications and change the running applications codes without re-execution. Our system can be further enhanced by using plug-in components with the above mechanisms. For example, with the aid of visualization components, our system can help users explore program behavior. In addition, all these activities can be performed in a collaborative way. This makes it also helpful for distant learning and program testing.

We identified an important issue when supporting a large scale networked virtual environment (NVE) with a server cluster. This issue is similar to the process migration issue on the parallel computing study and we refer it as the avatar migration problem. That is, when an avatar of an NVE is moving from one region managed by a server to another region managed by a different server, the client site may perceive abrupt screen change due to the different contents managed by these two servers. This paper proposes equations to solve this problem and elaborates the proposed avatar migration mechanism with state diagrams. The implementing architecture is also given in this paper. Our experiments that successfully show the efficiency of the proposed mechanism are given at the last.

Abstract We describe the design and implementation of system architecture to support object introspection in C++. In this system, information is collected by parsing class declarations, and is used to build a supporting environment for object introspection. Our approach is non‐intrusive because it requires no changes in the original class declarations and libraries; hence, binary compatibility between objects before and after the addition of introspective capability is ensured. This is critical if one wants to integrate third‐party class libraries, which are often supplied as black boxes and allow no modification, into highly dynamic applications. We present two applications: the first is automatic I/O support for C++ objects, and the other is interactive exercise of dynamically loaded C++ class libraries. Copyright © 2001 John Wiley & Sons, Ltd.

In this paper, we address the problem of minimizing channel contention of linear-complement communication on wormhole-routed hypercubes. Our research reveals that, for traditional routing algorithms, the degree of channel contention of a linear-complement communication can be quite large. To solve this problem, we propose an alternative approach, which applies processor reordering mapping at compile time. In this compiler approach, processors are logically reordered according to the given communication(s) so that the new communication(s) can be efficiently realized on the hypercube network. It is proved that, for any linear-complement communication, there exists a reordering mapping such that the new communication has minimum channel contention. An O(n/sup 3/) algorithm is proposed to find such a mapping for an n-dimensional hypercube. An algorithm based on dynamic programming is also proposed to find an optimal reordering mapping for a set of linear-complement communications. Several computer simulations have been conducted and the results clearly show the advantage of the proposed approach.

For distributed memory parallel computers, broadcast operations are widely used in a variety of applications. In this paper we propose an efficient algorithm for broadcasting on an all-port wormhole-routed 2D torus with arbitrary size. The underlying network is assumed to support only the dimension-ordered unicast. By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can greatly reduce the number of message-passing steps. In addition, it can be proved to be depth contention-free. The performance study in this paper clearly shows the advantage of the proposed algorithm.

For distributed memory parallel computers, broadcast operations arc widely used in a variety of applications.In this paper, we propose an eflicicnt algorithm for broadcasting on an all-port wormhole-routed 2D torus.The underlying network is assumed to support only the dimensionordered unicast routing.By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can be proved to be depth contention-free, and needs only n steps for broadcasting on a 2d~2" torus.Furthermore, the software latency is also reduced by appropriately overlaying the messages sent out by the same node in each step.The timing analysis and the computer simulation conducted in this paper clearly show the performance im provement of the proposed algorithm.

We describe the design and implementation of system architecture to support object introspection in C++. In this system, information is collected by parsing class declarations, and used to build a supporting environment for object introspection. Our approach is nonintrusive because it requires no change to the original class declarations and libraries, and it guarantees compatibility between objects before and after the addition of introspective capability. This is critical if one wants to integrate third-party class libraries, which are often supplied as black boxes and allow no modification, into highly dynamic applications. We show two applications: automatic I/O support for C++ objects; and an interactive exercise of dynamically loaded C++ class libraries.

Given a set of classes as input, a class exerciser, with its easy-to-use graphical user interface, allows users to create objects for the given classes, invoke methods on specified objects and examine the contents of objects interactively. In other words, one can use a class exerciser to exercise and assess the various functions of classes conveniently. The class exerciser has many applications in object-oriented software development. In particular, it can be used as a tool for demonstration testing and maintenance all together. We also describe our design and implementation of a class exerciser, RunClass, for the programming language C++.

Article Free Access Share on A near-optimal broadcasting algorithm in all-port wormhole-routed hypercubes Authors: Chien-Min Wang Institute of Information Science, Academia Sinica, Nankang, Taipei, Taiwan Institute of Information Science, Academia Sinica, Nankang, Taipei, TaiwanView Profile , Chiu-Yu Ku Institute of Information Science, Academia Sinica, Nankang, Taipei, Taiwan Institute of Information Science, Academia Sinica, Nankang, Taipei, TaiwanView Profile Authors Info & Claims ICS '95: Proceedings of the 9th international conference on SupercomputingJuly 1995 Pages 147–153https://doi.org/10.1145/224538.224554Published:03 July 1995Publication History 6citation99DownloadsMetricsTotal Citations6Total Downloads99Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper, an approach to the problem of exploiting parallelism within nested loops is proposed. The proposed method first finds out all the initially independent computations, and then, based on them, identifies the valid partitioning bases to partition the entire iteration space of the loop nest. Because the shape of the iteration space is taken into account, pseudo-dependence relations are eliminated and hence more parallelism is exploited. Our approach provides a systematic method to maximize the degree of fine- or coarse-grain parallelism and is free from the open question of how to combine different loop transformations for the goal of maximizing parallelism. It is also shown that our approach can exploit more parallelism than other related work and have many advantages over them.

An important issue for the efficient use of multiprocessor systems is the assignment of parallel processors to nested parallel loops. It is desirable for a processor assignment algorithm to be fast and always generate an optimal processor assignment. The paper proposes two efficient algorithms to decide the optimal number of processors assigned to each individual loop. Efficient parallel counterparts of these two algorithms are also presented. These algorithms not only always generate an optimal processor assignment, but also are much faster than the exiting optimal algorithm in the literature. The paper discusses improving the performance of parallel execution by transforming a nested parallel loop into a semantically equivalent one. Three loop transformations are investigated. It is observed that, in most cases, the parallel execution time is improved after applying these transformations.>

By analyzing the dependences between instances, the authors propose a new compiler technique called cycle breaking for parallelizing nested loops. For a single dependence cycle, it extracts more parallelism than two similar techniques. Several versions of cycle braking are presented to extract parallelism within a nested loop by linearizing its multidimensional iteration space. It is observed that the order in which loops are linearized can dramatically affect the parallelism extracted by cycle breaking. Two loop reordering transformations are investigated. Methods to find the optimal linearization order of loops are proposed. These techniques can enhance the parallelism of a nested loop.>