The rapid growth of Ethereum has made it more important to quickly and accurately detect smart contract vulnerabilities. While machine learning-based methods have shown some promise, many still rely on rule-based preprocessing designed by domain experts. Rule-based preprocessing methods often discard crucial context from the source code, potentially causing certain vulnerabilities to be overlooked and limiting adaptability to newly emerging threats. We introduce BugSweeper, an end-to-end deep learning framework that detects vulnerabilities directly from the source code without manual engineering. BugSweeper represents each Solidity function as a Function-Level Abstract Syntax Graph (FLAG), a novel graph that combines its Abstract Syntax Tree (AST) with enriched control-flow and data-flow semantics. Then, our two-stage Graph Neural Network (GNN) analyzes these graphs. The first-stage GNN filters noise from the syntax graphs, while the second-stage GNN conducts high-level reasoning to detect diverse vulnerabilities. Extensive experiments on real-world contracts show that BugSweeper significantly outperforms all state-of-the-art detection methods. By removing the need for handcrafted rules, our approach offers a robust, automated, and scalable solution for securing smart contracts without any dependence on security experts.

Account-based blockchains can suffer from huge state data as the number of accounts soars, as in the current Ethereum. This makes it hard to synchronize and operate as a full node to verify transactions, or as an archive node to maintain all archive data for provenance queries. The problem is mostly caused by the state trie, a tree-like data structure to store account states in its leaves, where an account has a path key to follow to access the account. Whenever an account is updated in the state trie, all trie nodes along the path key from the leaf to the root are newly created, which causes a data explosion. In this paper, we propose a novel state optimization technique called Ethane. Instead of assigning a fixed, hash-based path key for an account as in Ethereum, Ethane assigns a variable, counter-based path key. So, when a transaction creates or updates an account, Ethane creates a new leaf node for the account and assigns a path key of the next counter value, which has an effect of adding the leaf to the rightmost slot of the trie. This compact trie maximizes common parent nodes and minimizes the creation of new non-leaf nodes, significantly reducing the archive data size. In addition, Ethane maintains two types of compact tries: an active trie for frequently updated accounts and an inactive trie for dormant accounts not updated for a long time (e.g., three months). Dormant accounts are transferred to the inactive trie but can be reactivated at any time via a restore transaction. When synchronizing as a full node, we only need to download the active trie and the rightmost path of the inactive trie to function fully, significantly reducing both storage requirements and synchronization overhead. Our evaluation shows that Ethane can downsize the archive state data by 60–85% and the current state trie by 60–94%. It also doubles the block execution performance.

Backward error analysis allows finding a modified loss function, which the parameter updates really follow under the influence of an optimization method. The additional loss terms included in this modified function is called implicit regularizer. In this paper, we attempt to find the implicit regularizer for various federated learning algorithms on non-IID data distribution, and explain why each method shows different convergence behavior. We first show that the implicit regularizer of FedAvg disperses the gradient of each client from the average gradient, thus increasing the gradient variance. We also empirically show that the implicit regularizer hampers its convergence. Similarly, we compute the implicit regularizers of FedSAM and SCAFFOLD, and explain why they converge better. While existing convergence analyses focus on pointing out the advantages of FedSAM and SCAFFOLD, our approach can explain their limitations in complex non-convex settings. In specific, we demonstrate that FedSAM can partially remove the bias in the first-order term of the implicit regularizer in FedAvg, whereas SCAFFOLD can fully eliminate the bias in the first-order term, but not in the second-order term. Consequently, the implicit regularizer can provide a useful insight on the convergence behavior of federated learning from a different theoretical perspective.

One of the chronic problems of deep-learning models is shortcut learning. In a case where the majority of training data are dominated by a certain feature, neural networks prefer to learn such a feature even if the feature is not generalizable outside the training set. Based on the framework of Neural Tangent Kernel (NTK), we analyzed the case of linear neural networks to derive some important properties of shortcut learning. We defined a “feature” of a neural network as an eigenfunction of NTK. Then, we found that shortcut features correspond to features with larger eigenvalues when the shortcuts stem from the imbalanced number of samples in the clustered distribution. We also showed that the features with larger eigenvalues still have a large influence on the neural network output even after training, due to data variances in the clusters. Such a preference for certain features remains even when a margin of a neural network output is controlled, which shows that the max-margin bias is not the only major reason for shortcut learning. These properties of linear neural networks are empirically extended for more complex neural networks as a two-layer ReLU FC network and a ResNet-18.

We propose a trusTEE-chain, a highly scalable payment system on a centralized host with trusted execution environments (TEEs) that can provide confidentiality and integrity. Our implementation of trusTEE-chain called RouTEE is an open-sourced TEE application which can provide a unified solution for the existing issues of payment systems. That is, although RouTEE is run by a host, its data including payment details can be concealed from the host. Also, RouTEE does not require its own collateral, but receives deposits from users and makes payments. Users do not have to verify the whole blockchain but only the block headers asynchronously, and they can go indefinitely offline without worrying about financial losses. Finally, RouTEE is highly scalable since its payment throughput is limited only by the TEE performance. Although TEEs can simplify the solution, TEEs alone are not enough because the host can possibly misbehave by feeding fake blocks to RouTEE or aborting its operation. By introducing a novel protocol and incentive model, RouTEE makes a rational host behave honestly. We also propose solutions for fault failures, compromised TEEs, and irrational hosts. RouTEE works for any UTXO-based blockchain and requires only the digital signatures, thus highly portable. Our implementation of RouTEE using Intel SGX on Bitcoin shows that RouTEE achieves a high throughput even with frequent data backups, for more than 150K users.

Web app migration refers to capturing a snapshot of the execution state of a web app on a device and restoring it on another device to continue its execution for cross-device liquid computing. Although web apps are relatively easy to migrate due to their high portability, there is a JavaScript language feature called closure that complicates the migration since it requires migrating the variable states of already-finished outer functions. One approach to web app migration is to instrument the source code to trace the closure variables, yet this often suffers from performance slowdown, especially for multiple migrations. In this paper, we propose a new instrumentation-based technique called Disclosure, which moves the declarations of closure variables to a managed data structure and replaces the closure variables with the corresponding references to the data structure. This technique can improve runtime performance while enhancing security. We evaluated our work with eight Octane benchmarks and four real web apps. The runtime performance penalty due to Disclosure is 0–15%, which is a significant improvement over the results of the latest instrumentation-based work that supports similar deep closures and multiple migrations to Disclosure. Furthermore, real web apps are demonstrated to migrate seamlessly, even multiple times. Finally, Disclosure can hide data from exposure during migration with a secure migration technique using data encryption.

Irregularly structured registers are hard to abstract and allocate. Partitioned Boolean quadratic programming (PBQP) is a useful abstraction to represent complex register constraints, even those in highly irregular processors of automated test equipment (ATE) of DRAM memory chips. The PBQP problem is NP-hard, requiring a heuristic solution. If no spill is allowed as in ATE, however, we have to enumerate more to find a solution rather than to approximate, since a spill means a total compilation failure. We propose solving the PBQP problem with deep reinforcement learning (Deep-RL), more specifically, a model-based approach using Monte Carlo tree search and deep neural network as used in Alphazero, a proven Deep-RL technology. Through elaborate training with random PBQP graphs, our Deep-RL solver could cut the search space sharply, making an enumeration-based solution more affordable. Furthermore, by employing backtracking with a proper coloring order, Deep-RL can find a solution with modestly-trained neural networks with even less search space. Our experiments show that Deep-RL can successfully find a solution for 10 product-level ATE programs while searching much fewer (e.g., 1/3,500) states than the previous PBQP enumeration solver. Also, when applied to C programs in llvm-test-suite for regular CPUs, it achieves a competitive performance to the existing PBQP register allocator in LLVM.

Ethereum is a popular account-based blockchain whose number of accounts and transactions has skyrocketed, causing its data explosion. As a result, ordinary clients using PCs or smartphones cannot easily bootstrap as a full node, but rely on other full nodes to verify transactions, thus being exposed to security risks. The most serious overhead is caused by synchronizing the state of all accounts in the block's state trie, which takes several tens of gigabytes. Observing that more than 95% of the accounts are dormant, we propose a novel state optimization technique, named Ethanos. Ethanos downsizes the state trie by periodically emptying it, and then re-build it only with the active accounts used in the period's transactions. Ethanos runs transactions using the accounts available in the current period's state trie as well as those available at the end of the previous period's state trie. For an account in neither of the tries, the account first restores itself by transmitting a restore transaction. One important result of this state management is that a node can now bootstrap only with the latest period's state trie, yet can fully verify all transactions thereafter. We evaluated Ethanos with real Ethereum transactions for 300,000 blocks from the 7.0 million block, with a one-week period of emptying the state trie. Our result shows that Ethanos can sharply reduce the state trie, with only a tiny fraction of the restore transactions. More importantly, unlike the Ethereum state trie which continues to grow as time goes on, the Ethanos state trie size at the end of each period is bounded by a few hundred MB, when there are more than one million, one-week-active accounts.

Test-pattern programs are for testing DRAM memory chips. They run on a special embedded system called automated test equipment (ATE). Each ATE manufacturer provides its own programming language, which is mostly low level, thus accessing the registers in the ATE directly. The register structure of each ATE is quite different and highly irregular. Since DRAM chipmakers are often equipped with diverse ATEs from different manufacturers, they employ automatic translation of a program developed for one ATE to a program for different ATEs. This raises an irregular register allocation problem during translation. This article proposes a solution based on partitioned Boolean quadratic programming (PBQP). PBQP has been used for a number of compiler optimizations, including paired register allocation , which our ATE register allocation also requires. Moreover, the interleaved processing in ATE incurs complex register constraints, which we could also formulate elegantly with PBQP. The original PBQP solver is not quite appropriate to use, though, since ATE register allocation does not allow spills, so we devised a more elaborate PBQP solver that trades off the allocation time and allocation search space, to find a solution in a reasonable amount of time. Our experimental results with product-level pattern programs show that the proposed register allocator successfully finds valid solutions in all cases, in the order of tenths of seconds.

Emerging mobile applications, such as cognitive assistance based on deep neural network (DNN), require low latency as well as high computation power. To meet these requirements, edge computing (also called fog computing) has been proposed, which offloads computations to edge servers located near mobile clients. This paradigm shift from cloud to edge requires new computing infrastructure where edge servers are pervasively distributed over a region. This paper presents PerDNN, a system that executes DNNs of mobile clients collaboratively with pervasive edge servers. PerDNN dynamically partitions DNN computation between a client and an edge server to minimize execution latency. It predicts the next edge server the client will visit, calculates a speculative partitioning plan, and transfers the server-side DNN layers to the predicted server in advance, which reduces the initialization overhead needed to start offloading, thus avoiding cold starts. We do not incur excessive network traffic between edge servers, though, by migrating only a tiny fraction of the server-side DNN layers with negligible performance loss. We also use GPU statistics of edge servers for DNN partitioning to deal with the resource contention caused by multi-client offloading. In the simulation with human trace datasets and execution profile of real hardware, PerDNN reduced the occurrence of cold starts by up to 90%, achieving 58% higher throughput when clients change their offloading servers, compared to a baseline without proactive DNN transmission.

Following the recent success of deep neural networks (DNN) on video computer vision tasks, performing DNN inferences on videos that originate from mobile devices has gained practical significance. As such, previous approaches developed methods to offload DNN inference computations for images to cloud servers to manage the resource constraints of mobile devices. However, when it comes to video data, communicating information of every frame consumes excessive network bandwidth and renders the entire system susceptible to adverse network conditions such as congestion. Thus, in this work, we seek to exploit the temporal coherence between nearby frames of a video stream to mitigate network pressure. That is, we propose ShadowTutor, a distributed video DNN inference framework that reduces the number of network transmissions through intermittent knowledge distillation to a student model. Moreover, we update only a subset of the student’s parameters, which we call partial distillation, to reduce the data size of each network transmission. Specifically, the server runs a large and general teacher model, and the mobile device only runs an extremely small but specialized student model. On sparsely selected key frames, the server partially trains the student model by targeting the teacher’s response and sends the updated part to the mobile device. We investigate the effectiveness of ShadowTutor with HD video semantic segmentation. Evaluations show that network data transfer is reduced by 95% on average. Moreover, the throughput of the system is improved by over three times and shows robustness to changes in network bandwidth.

Mobile web platforms are facing new demands for emerging applications, such as machine learning or augmented reality, which require significant computing powers beyond that of current mobile hardware. Computation offloading can accelerate these apps by offloading the computation-intensive parts of an app from a client to a powerful server. Unfortunately, previous studies of offloading in the field of web apps have a limitation for the offloading target code or require complex user annotations, hindering the widespread use of offloading in web apps. This article proposes a novel offloading system for web apps, which can simplify the offloading process by sending and receiving the execution state of a running web app in the form of another web app called the snapshot . Since running the snapshot restores the whole app state and continues the execution from the point where it was saved, we can offload regular web app computations that affect the DOM state as well as the JavaScript state, and we do not have to pre-install the app binary at the server. Moreover, the snapshot does not require any annotations to be captured, making computation offloading more transparent to app developers. We qualitatively compared the proposed system with previous approaches in terms of programming difficulty and the scope of offloadable codes. In addition, we implemented the proposed system based on a WebKit browser and evaluated the offloading performance with five computation-intensive web apps. Our system achieved significant speedup (from 1.7 to approximately 9.0) in all of the apps, compared to local execution, which proves the feasibility of the proposed approach.

Reducing the loading time of a web app is important for a better user experience. The loading time includes a large amount of JavaScript execution, often composed of the execution of the global code in the script tags followed by the execution of event handlers. One approach to accelerate the app loading is saving the already-loaded execution state of JavaScript objects in a file called the snapshot in advance. Then, we start an app by copying the objects in the snapshot to the JavaScript heap directly, instead of executing JavaScript code to create them. Unfortunately, existing works save only the execution state of the global code in the snapshot, not that of the event handlers. Also, JavaScript code whose execution may change the DOM (Document Object Model) tree is not saved in the snapshot, limiting the coverage of the snapshot.

Future mobile applications, such as mobile cloud gaming or augmented reality, require not only high computation power but strict latency constraints. To provide computing resources with ultra-low latency, a new form of cloud infrastructure called edge cloud has been proposed, which distributes computing servers at the edges of the network. A primary concern of edge cloud is that a physical server running a service can change as the client moves, so the service has to be quickly migrated between servers for seamless computation offloading.

For the testing of memory chips, automatic test equipment (ATE) uses pattern program to generate a bit vector for each clock. Pattern programs are not portable across different ATEs, requiring a different program for each ATE, even when they test the same memory chip. Many solutions and in-house tools have been proposed for this portability problem, but they were not completely successful. This paper proposes PaTran, a software translation platform for pattern programs. PaTran employs intermediate representation (IR) based on the pattern itself, generated by simulating the source pattern program. It synthesizes the target program by reconstructing the program statements from the IR. Since the IR size is huge for product-level programs, PaTran employs a concise form of IR, embedded with repetition information. Implementation of PaTran is based on the web and server-client model.

JavaScript execution is heavily used during the loading of web apps, taking a substantial portion of the app loading time. To accelerate JavaScript execution, snapshot-based app loading has been proposed [5, 17]. We take a snapshot of the JavaScript objects in the heap at some point during app loading (which we call snapshot point) and save them in a file in advance. Then, we start app loading by copying the objects in the snapshot to the heap directly, skipping JavaScript execution to create those objects. One issue is that the JavaScript execution state at the snapshot point should be the same at every app loading. If JavaScript execution included in the snapshot is involved with some nondeterminism (e.g., use random function or current time/location), snapshot-based app loading might be inapplicable since the loaded state might differ each time.

As web pages and web apps increasingly include heavy JavaScript code, JavaScript performance has been a critical issue. Modern JavaScript engines achieve a remarkable performance by employing tiered-execution architecture based on interpreter, baseline just-in-time compiler (JITC), and optimizing JITC. Unfortunately, they suffer from a substantial compilation overhead, which can take more than 50% of the whole running time. A simple idea to reduce the compilation overhead is ahead-of-time compilation (AOTC), which reuses the code generated in the previous run. In fact, existing studies that reuse the bytecode generated by the interpreter or the machine code generated by the baseline JITC have shown tangible performance benefits [12, 31, 41]. However, there has been no study to reuse the machine code generated by the optimizing JITC, which heavily uses profile-based optimizations, thus not easily reusable. We propose a novel AOTC that can reuse the optimized machine code for high-performance JavaScript engines. Unlike previous AOTCs, we need to resolve a few challenging issues related to reusing profile-based optimized code and relocating dynamic addresses. Our AOTC improves the performance of a commercial JavaScript engine by 6.36 times (max) and 1.99 times (average) for Octane benchmarks, by reducing the compilation overhead and by running the optimized code from the first invocation of functions. It also improves the loading time of six web apps by 1.28 times, on average.

An Intermediate Representation (IR) used by compilers is normally generated statically , as a result of parsing or analyzing the source program. This paper proposes a completely different type of IR, generated as a result of running the source program, the output-based IR . There is a practical translation problem where such an IR is useful, in the domain of test-pattern programs . Test-pattern programs run on ATE (automatic test equipment), a special embedded system to test semiconductors such as DRAMs. They generate a pattern for each clock, a bit vector input to the pins of the chip. One issue is that different ATEs require different programming since each ATE manufacturer has its own programming language. Nonetheless, we should be able to test a memory chip on different ATEs as long as they generate the same patterns with the same speed. Therefore, a memory chipmaker wants to make a pattern program portable across ATEs, to fully utilize their ATE resources. One solution is translating between pattern programs, for which we need an IR since there are multiple source ATEs and target ATEs. Instead of a conventional, static IR, we propose using the output pattern itself as an IR. Since the pattern is independent of ATEs and easily obtainable, the output-based IR obviates designing a static IR considering all ATE programming languages and hardware differences. Moreover, we might synthesize a better target program from the IR, more optimized to the target ATE. However, the full pattern generated by a product-level pattern program is huge, so we propose using an IR of abbreviated patterns, annotated with the repetition information obtained while executing the source program. Our experimental results with product-level pattern programs show that our approach is feasible.

Current wisdom to run computation-intensive deep neural network (DNN) on resource-constrained mobile devices is allowing the mobile clients to make DNN queries to central cloud servers, where the corresponding DNN models are pre-installed. Unfortunately, this centralized, cloud-based DNN offloading is not appropriate for emerging decentralized cloud infrastructures (e.g., cloudlet, edge/fog servers), where the client may send computation requests to any nearby server located at the edge of the network. To use such a generic edge server for DNN execution, the client should first upload its DNN model to the server, yet it can seriously delay query processing due to long uploading time. This paper proposes IONN (Incremental Offloading of Neural Network), a partitioning-based DNN offloading technique for edge computing. IONN divides a client's DNN model into a few partitions and uploads them to the edge server one by one. The server incrementally builds the DNN model as each DNN partition arrives, allowing the client to start offloading partial DNN execution even before the entire DNN model is uploaded. To decide the best DNN partitions and the uploading order, IONN uses a novel graph-based algorithm. Our experiments show that IONN significantly improves query performance in realistic hardware configurations and network conditions.

Due to the portability advantage of web apps, we can easily save the app execution state at a device and restore it at another device, allowing app migration. Since the execution of the application includes JavaScript internal states such as closures or event handlers, how to extract them is an issue. One approach is having the browser to provide new APIs [1], which allows fast migration, but requires modification of the browser. The other approach is instrumenting the web app source code [2], [3], which allows using the existing browser, however, suffering from the performance slowdown due to the overhead of instrumented code. This paper proposes a new instrumentation-based approach, which performs faster. The key idea is to introduce a reference table which is used to keep information of closures and event handlers at runtime by our instrumented code whose overhead is small. The reference table can be easily serialized as JavaScript code, and its execution at the target device allows efficient restoration of the execution state. Our preliminary experimental result shows that the performance of our instrumented code is almost the same as the original code.

Machine leaning apps require heavy computations, especially with the use of the deep neural network (DNN), so an embedded device with limited hardware cannot run the apps by itself. One solution for this problem is to offload DNN computations from the client to a nearby edge server. Existing approaches to DNN offloading with edge servers either specialize the edge server for fixed, specific apps, or customize the edge server for diverse apps, yet after migrating a large VM image that contains the client's back-end software system. In this paper, we propose a new and simple approach to offload DNN computations in the context of web apps. We migrate the current execution state of a web app from the client to the edge server just before executing a DNN computation, so that the edge server can execute the DNN computation with its powerful hardware. Then, we migrate the new execution state from the edge server to the client so that the client can continue to execute the app. We can save the execution state of the web app in the form of another web app called the snapshot, which immensely simplifies saving and restoring the execution state with a small overhead. We can offload any DNN app to any generic edge server, equipped with a browser and our offloading system. We address some issues related to offloading DNN apps such as how to send the DNN model and how to improve the privacy of user data. We also discuss how to install our offloading system on the edge server on demand. Our experiment with real DNN-based web apps shows that snapshot-based offloading achieves a promising performance result, comparable to running the app entirely on the server.

Summary Web applications (apps) are programs created by web technologies such as HTML, CSS, and JavaScript. Web apps can be executed on any platform that supports a web browser. Such portability allows an interesting user experience called app migration, which can save an app's execution state to a file called snapshot, transmit it to another device, and continue the execution using the snapshot. However, existing approaches save all the states of the current app, regardless of its relevance to an app's state, making the snapshot size and snapshot creation time infeasibly large. For example, web apps are often programmed using web frameworks such as jQuery, which are libraries written in JavaScript to support app developments. We found that most objects created by frameworks during their initialization are not relevant to an app's state. Hence, one idea to reduce the snapshot size is not saving those framework objects in the snapshot but creating them after migration via re‐initialization. Unfortunately, this is not always straightforward since the framework objects are intermingled with the app objects in the heap, possibly pointing to each other. To resolve this, we separated app objects that are attached to framework objects by monitoring app's execution and saved them to the snapshot. This paper proposes such a framework separated migration technique, with optimization to reduce the overhead, especially related to monitoring app's execution. With our approach, we could reduce the snapshot size by 89.1% on average and shorten the migration time by 47.6%, increasing the feasibility of app migration.

JavaScript1 is heavily used in the web, yet it is much slower than other languages. To improve the JavaScript performance, ahead-of-time compilation (AOTC) has been used, either to reuse the bytecode or the machine code generated by the baseline just-in-time compilation (JITC). JavaScript engines today employ high-performance optimizing JITC. So, we propose an AOTC that reuses the code generated by the optimizing JITC. It is more challenging than existing AOTCs since we need to handle more complex address relocation issues. Our preliminary evaluation shows that the proposed AOTC is promising, though.

Due to its high portability and simplicity, web application (app) based on HTML/JavaScript/CSS has been widely used for various smart-device platforms. To take advantage of its wide platform pool, a new idea called app migration has been proposed for the web platform. Web app migration is a framework to serialize a web app running on a device and restore it in another device to continue its execution. In JavaScript semantics, one of the language features that does not allow easy app migration is a closure. A JavaScript function can access variables defined in its outer function even if the execution of the outer function is terminated. It is allowed because the inner function is created as a closure such that it contains the outer function's environment. This feature is widely used in web app development because it is the most common way to implement data encapsulation in web programming. Closures are not easy to serialize because environments can be shared by a number of closures and environments can be created in a nested way. In this paper, we propose a novel approach to fully serialize closures. We created mechanisms to extract information from a closure's environment through the JavaScript engine and to serialize the information in a proper order so that the original relationship between closures and environments can be restored properly. We implemented our mechanism on the WebKit browser and successfully migrated Octane benchmarks and seven real web apps which heavily exploit closures. We also show that our mechanism works correctly even for some extreme, closure-heavy cases.

Java virtual machine (JVM) has recently evolved into a general-purpose language runtime environment to execute popular programming languages such as JavaScript, Ruby, Python, and Scala. These languages have complex non-Java features, including dynamic typing and first-class function, so additional language runtimes (engines) are provided on top of the JVM to support them with bytecode extensions. Although there are high-performance JVMs with powerful just-in-time (JIT) compilers, running these languages efficiently on the JVM is still a challenge. This article introduces a simple and novel technique for the JVM JIT compiler called exceptionization to improve the performance of JVM-based language runtimes. We observed that the JVM executing some non-Java languages encounters at least 2 times more branch bytecodes than Java, most of which are highly biased to take only one target. Exceptionization treats such a highly biased branch as some implicit exception-throwing instruction. This allows the JVM JIT compiler to prune the infrequent target of the branch from the frequent control flow, thus compiling the frequent control flow more aggressively with better optimization. If a pruned path were taken, then it would run like a Java exception handler, that is, a catch block. We also devised de-exceptionization , a mechanism to cope with the case when a pruned path is executed more often than expected. Since exceptionization is a generic JVM optimization, independent of any specific language runtime, it would be generally applicable to other language runtimes on the JVM. Our experimental result shows that exceptionization accelerates the performance of several non-Java languages. For example, JavaScript-on-JVM runs faster by as much as 60% and by 6% on average, when experimented with the Octane benchmark suite on Oracle’s latest Nashorn JavaScript engine and HotSpot 1.9 JVM. Furthermore, the performance of Ruby-on-JVM shows an improvement by as much as 60% and by 6% on average, while Python-on-JVM improves by as much as 6% and by 2% on average. We found that exceptionization is more effective to apply to the branch bytecode of the language runtime itself than the bytecode corresponding to the application code or the bytecode of the Java class libraries. This implies that the performance benefit of exceptionization comes from better JIT compilation of the language runtime of non-Java languages.

Summary Java just‐in‐time compilers often compile only hot methods because the compilation overhead is a part of the running time. This requires precise and efficienthot spot detection, which includes distinguishing hot methods from cold ones, detecting them as early as possible, and paying a small detection overhead. Hot spot detection is especially important in embedded applications because they show more of a start‐up phase behavior of a regular application where methods are not executed heavily, so the hot methods are not definite. Because a long‐running method is likely to be a hot method, we can detect a hot method by measuring its running time during interpretation. However, precise measurement of the running time during execution is too expensive, especially in embedded systems, so many counter‐based heuristics have been proposed to estimate it such as Oracle's HotSpot heuristic. One problem is that although the overhead of these heuristics is low, they do not estimate the running time precisely, which may lead to imprecise hot spot detection.This paper proposes a new hot spot detection heuristic calledflow‐sensitive runtime estimation, which can estimate the running time more precisely than others with a relatively low overhead. It only counts important bytecode instructions dynamically, but it can obtain the precise count ofallinterpreted bytecode instructions with a simple arithmetic calculation. We also propose a static analysis technique to predict those hot methods which spends a huge execution time once invoked, so as to compile them at their first invocation. Our experimental results show that these techniques can improve the performance by as much as an average of 7.4% compared with the HotSpot heuristic for the benchmarks when they run once, which is often regarded as showing the start‐up phase behavior. Even for real embedded Java applications such as the digital TV Java Xlet applications, our techniques can improve the user response time by an average of 7.1%. Copyright © 2015 John Wiley & Sons, Ltd.

JavaScript is a dynamic language mainly used as a client-side web script. Nowadays, web is evolving into an application platform with its web apps , and JavaScript increasingly undertakes complex computations and interactive user interfaces, requiring a high-performance JavaScript engine. There have been many optimizations for efficient JavaScript engines, but one component that has not been optimized much is JavaScript parsing . A JavaScript function needs to be parsed before being executed, and the parsing overhead takes a substantial portion of JavaScript execution time for web apps, especially during app loading . This article proposes concurrent parsing of JavaScript, which performs the parsing of JavaScript functions in advance on different threads, while the main thread is executing the parsed JavaScript functions. This can hide the parsing overhead from the main execution thread, reducing the JavaScript execution time, thus reducing the overall app loading time. More specifically, we separated JavaScript parsing and made it run on different threads without violating the execution semantics of JavaScript. We also designed an efficient multi-threaded parsing architecture, which reduces the synchronization overhead and schedules the parsing requests appropriately. Finally, we explored two methods of choosing the target functions for concurrent parsing: one based on profiled information and the other based on speculative heuristics. We performed experiments on the WebKit browser with the JSC engine for real web apps. The result shows that the proposed concurrent parsing can improve the JavaScript performance during app loading by as much as 64% and by 39.7% on average. This improves the whole app loading performance tangibly, by as much as 32.7% and by 18.2%, on average.

Web applications (apps) are programmed using HTML, CSS, and JavaScript. Web apps allow a faster app development based on existing web technology and a better portability since they are runnable on any device where a web browser is installed. Unfortunately, web apps are involved with a performance issue due to JavaScript, because its dynamic typing, function object, and prototype are difficult to execute efficiently, so even just-in-time compilers do not help much. In this paper, we propose a new approach to accelerate a web app, especially its loading time. Generally, running an app is composed of app loading to initialize the app, followed by event-driven computation. If the same job needs to be done to load an app, especially the execution of the same JavaScript code, it will be better to save the JavaScript execution state in advance and to start the app from the saved state. In fact, app loading is often involved with the initialization of the web framework such as j Query [1], Enyo [2], or Ext JS [3] where many JavaScript objects are created. Also, app-specific objects are created during app loading. If we save the initialized state of these objects in the form of a snapshot and start app loading by restoring the objects from the snapshot, we would accelerate app loading. We actually implemented the idea for the above three web frameworks, which lead to a 77% reduction of their initialization time. This can reduce the whole app loading time for an Enyo app by at least 20%, which could be noticed tangibly.

As the web technology advances, web applications, executable on any devices where a web browser is installed, have become pervasive. However, running heavy web applications in the mobile devices is challenging, because of their resource constraints and poor network environments. One of the trials to overcome such restrictions is computation offloading. Computation offloading is the technique migrating computations from client to server to exploit the powerful resources of the server. We observed some former approaches to the computation offloading, and found out they placed a huge burden on programmers to write annotations and substantially limited the computations to be offloaded. In order to overcome these problems, we propose an offloading system transferring the states without annotations and giving programmers freedom to use JavaScript features and DOM (Document Object Model) API in the offloaded computations. Our approach is based on the technique called snapshot, which safely saves and restores the states of web applications. The snapshot-based approach allows the offloaded computations to use various features such as a closure, and DOM API. In the web applications using open source JavaScript libraries, our offloading system successfully offloaded the event handlers using closure variables and DOM APIs, achieving a speedup up to 7.2.

Web applications (apps) are programmed using HTML5, CSS, and JavaScript, and are distributed in the source code format. Web apps can be executed on any devices where a web browser is installed, allowing one-source, multi-platform environment. We can exploit this advantage of platform independence for a new user experience called app migration, which allows migrating an app in the middle of execution seamlessly between smart devices. This paper proposes such a migration framework for web apps where we can save the current state of a running app and resume its execution on a different device by restoring the saved state. We save the web app's state in the form of a snapshot, which is actually another web app whose execution can restore the saved state. In the snapshot, the state of the JavaScript variables and DOM trees are saved using the JSON format. We solved some of the saving/restoring problems related to event handlers and closures by accessing the browser and the JavaScript engine internals. Our framework does not require instrumenting an app or changing its source code, but works for the original app. We implemented the framework on the Chrome browser with the V8 JavaScript engine and successfully migrated non-trivial sample apps with reasonable saving and restoring overhead. We also discuss other usage of the snapshot for optimizations and user experiences for the web platform.

The Java-based software platform for interactive digital TV (DTV) is composed of the system/middleware class statically installed on the DTV set-top box and the xlet applications dynamically downloaded from the TV stations. The xlet application includes Java classes and image/text files. The xlets are executed only when the TV viewer initiates an interaction, even if the xlets have been completely downloaded. To achieve high performance on this dual-component, user-initiated system, existing just-in-time (JIT) compilation and optimization is not enough; instead, ahead-of-time and idle-time compilation and optimization are also needed, requiring a hybrid compilation and optimization environment. We constructed such a hybrid environment for a commercial DTV software platform and evaluated it using real, on-air xlet applications. Our experimental results show that the proposed hybrid environment can improve the DTV Java performance by more than three times, compared to the JIT-only environment, with little change to other DTV behavior.

Java embedded systems often include Java middleware classes installed on the client device. For higher performance, they can be compiled into machine code before runtime using an ahead-of-time compiler (AOTC). There are many approaches to AOTC, yet a bytecode-to-C (b-to-C) AOTC which translates the bytecode into the C code and then compiles it using an existing optimizing compiler such as gcc would be the most straightforward one. This paper explores a few important design and optimization issues of a b-to-C AOTC, including the compilation form for the translated C code, the call interfaces among translated and interpreted Java methods, and Java-specific optimizations by the AOTC that can complement the gcc optimizations. We evaluate these issues with our b-to-C AOTC implemented on the MIPS platform for the Sun's CDC VM to understand their performance impact.

Smart phone's full web browsing requires a high-performance JavaScript engine because JavaScript execution takes a non-trivial portion of the loading time for many web sites. The current wisdom of speeding up JavaScript engine is simply turning on its just-in-time compilation (JITC), which compiles JavaScript code to machine code on the fly and executes it instead of interpretation. Unfortunately, we found that JITC actually increases the loading time tangibly for some JavaScript-heavy web pages compared to interpretation, while it can still reduce the running time for JavaScript benchmarks. We observed that the web page JavaScript behaves differently from the benchmark JavaScript in the sense that hot spots rarely exist. This would lower the reuse ratio of the compiled machine code, making the compilation overhead higher than its benefit. This is especially true for a JavaScript engine which compiles all executed functions at their first invocation, as the SFX engine in the WebKit. In order to overcome this problem, we introduce selective compilation to the SFX engine so as to compile only hot functions detected during interpretation. This reduces the slowdown of the SFX for web page JavaScript, while accelerating JavaScript benchmarks. However, selective compilation for web page JavaScript shows a different behavior from other environment, and we discuss it.

The Java software platform for the interactive digital TV (DTV) is composed of the system/middleware classes statically installed on the DTV set-top box and the xlet classes dynamically downloaded from the TV stations, where xlets are executed only when the TV viewer initiates the interaction. In order to achieve high performance on this dual-component, user-initiated system, existing just-in-time compilation is not enough, but idle-time compilation and optimization as well as ahead-of-time compilation are also needed, requiring a hybrid compilation and optimization environment. We constructed such a hybrid environment for a commercial DTV software platform and experimented with real, on-air xlet applications. Our experimental results show that the proposed hybrid environment can improve the DTV Java performance by as much as an average of 150%, compared to the JITC-only environment.

Abstract Many embedded Java platforms execute two types of Java classes: those installed statically on the client device and those downloaded dynamically from service providers at run time. For achieving higher performance, the static Java classes can be compiled into machine code by ahead‐of‐time compiler (AOTC) in the server, and the translated machine code can be installed on the client device. Unfortunately, AOTC cannot be applicable to the dynamically downloaded classes. This paper proposes client‐AOTC (c‐AOTC), which performs AOTC on the client device using the just‐in‐time compiler (JITC) module installed on the device, obviating the JITC overhead and complementing the server‐AOTC. The machine code of a method translated by JITC is cached on a persistent memory of the device, and when the method is invoked again in a later run of the program, the machine code is loaded and executed directly without any translation overhead. A major issue in c‐AOTC is relocation because some of the address constants embedded in the cached machine code are not correct when the machine code is loaded and used in a different run; those addresses should be corrected before they are used. Constant pool resolution and inlining complicate the relocation problem, and we propose our solutions. The persistent memory overhead for saving the relocation information is also an issue, and we propose a technique to encode the relocation information and compress the machine code efficiently. We developed a c‐AOTC on Sun's CDC VM reference implementation, and our evaluation results indicate that c‐AOTC can improve the performance significantly, as much as an average of 12% for EEMBC and 4% for SpecJVM98, with a persistent memory overhead of 1% on average. Copyright © 2008 John Wiley & Sons, Ltd.

Most embedded Java software platforms include a Java middleware installed on the client device. It can be optimized using the ahead-of-time compiler (AOTC), which translates the Java bytecode into the machine code before runtime. There are many approaches to AOTC, but a bytecode-to-C AOTC which translates the bytecode into C code and then compile it using an existing optimizing compiler such as gcc would be a practical one. This paper explores a few important design and optimization issues of a bytecode-to-C AOTC, including the compilation strategy for the translated C code, the call interfaces between Java methods, and Java-specific optimizations by the AOTC that can complement the gcc optimizations. We evaluate these issues with a bytecode-to-C AOTC to understand their performance impact.

A rotating register file is an architectural support for software pipelining, where many registers can be renamed at once when a rotating branch is executed. It has primarily been used for overcoming the cross-iteration register overwrites in modulo-scheduled, straight-line or if-converted loops. Recently, a new technique has been proposed to use rotating registers for loops with arbitrary control flows, scheduled by enhanced pipeline scheduling (EPS). EPS generates many hard-to-delete copies to overcome the cross-iteration register overwrites, but these copies may cause a stall in addition to taking resources. The proposed technique eliminates those copies by allocating rotating registers, avoiding a serious slowdown caused by them. Unfortunately, it could not eliminate enough copies, as much as those removed by the unroll-based copy elimination technique, although both techniques employ the same abstraction called an extended live range (ELR). This is due to the limitation that only a branch edge can be a rotating branch, while any edge can be an unrolling edge. In this paper, we propose an enhanced rotating register allocation technique where we can use more than one rotating branches in order to eliminate more copies. This requires an extension of the theory of ELR and the rotating register allocation algorithm. Our experimental results indicate that our proposed technique can eliminate 20% more copies than the previous technique, which results in a performance improvement as much as more than 10%.

Most Java just-in-time compilers (JITC) try to compile only hot methods since the compilation overhead is part of the running time. This requires precise and efficient hot spot detection, which includes distinguishing hot methods from cold methods, detecting them as early as possible, and paying a small runtime overhead for detection. A hot method could be identified by measuring its running time during interpretation since a long-running method is likely to be a hot method. However, precise measurement of the running time during execution is too expensive, especially in embedded systems, so many counter-based heuristics have been proposed to estimate it. The Simple heuristic counts only method invocations without any consideration of loops [1], while Sun's HotSpot heuristic counts loop iterations as well, but does not consider loop sizes or method sizes [2,14]. The static analysis heuristic estimates the running time of a method by statically analyzing loops or heavy-cost bytecodes but does not measure their dynamic counts [3]. Although the overhead of these heuristics is low, they do not estimate the running time precisely, which may lead to imprecise hot spot detection.

Language, Compiler and Tool Support for Embedded Systems \nProceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems \nSan Diego, California, USA

One of the most serious constraints of an embedded system is its limited memory, which requires small code size for embedded software. One popular method to reduce the code size is reducing the instruction encoding, such as the ARM THUMB or the MIPS-16 architectures. They employ shorter instructions by reducing the field width, including those of register operands. This obviously reduces the number of registers available for register allocation than in the original architecture, which can lead to more register spills, negatively affecting the code size. This paper proposes a simple architectural upgrade by reconstructing the original register file into register banks and by providing a bank change instruction. This can allow all of the original registers to be available for register allocation when the bank change instructions are added appropriately. For such a banked register file, we propose an efficient, region-based register bank allocation technique where appropriate regions are chosen first for bank changes, followed by conventional global register allocation. As a case study, we apply the idea to the ARM THUMB architecture and evaluate how the upgrade affects its overall code size. We found that the upgrade results in an average of 5.0% code size reduction for some of MiBench and MediaBench benchmarks, compared to the original THUMB code.

A Java bytecode-to-C ahead-of-time compiler (AOTC) can improve the performance of a Java virtual machine (JVM) by translating bytecode into C code, which is then compiled into machine code via an existing C compiler. Although AOTC is effective in embedded Java systems, a bytecode-to-C AOTC could not easily employ precise garbage collection (GC) due to a difficulty in making a GC map, which keeps information on where each root live object is located when GC occurs. This is one of the reasons why all previous JVMs using a bytecode-to-C AOTC employed conservative GC, which can lead to poorer GC performance with more frequent memory shortage, especially in embedded systems where memory is tight.In this paper, we propose a way of allowing precise GC in a bytecode-to-C AOTC by generating additional C code which collects GC map-equivalent information at runtime. In order to reduce this runtime overhead, we also propose two optimization techniques which remove unnecessary C code. Our experimental results on Sun's CVM indicate that we can support precise GC for bytecode-to-C AOTC with a relatively low overhead.

One of the most promising approaches to Java acceleration in embedded systems is a bytecode-to-C ahead-of-time compiler (AOTC). It improves the performance of a Java virtual machine (JVM) by translating bytecode into C code, which is then compiled into machine code via an existing C compiler. One important design issue in AOTC is efficient exception handling. Since the excepting point and the exception handler may locate in different methods on a call stack, control transfer between them should be streamlined, while an exception would be an "exceptional" event, so it should not slow down normal execution paths. Previous AOTCs often employed stack cutting based on a setjmp()/longjmp(), which we found is involved with too much overheads. This paper proposes a simpler solution based on an exception check after each method call, merged with garbage collection check for reducing its overhead. Our evaluation results on SPECjvm98 on Sun's CVM indicate that our technique can improve the performance of stack cutting by more than 25%.

Memory allocation is an important part of modern programming languages, including garbage-collected languages such as Java. We propose a fast memory allocation scheme for Java using lazy worst fit (LWF), where pointer increment is used as the primary allocation method and worst fit is used as a backup. We evaluated LWF on a working Java virtual machine with non-moving garbage collection, and the results show that LWF is practically useful since the overhead of fit allocation and the amount of fragmentation are low.

Traditional mark and sweep garbage collectors use time proportional to the heap size when sweeping memory, since all objects in the heap, dead or alive, must be traversed. Here we introduce a sweeping algorithm which traverses only the live objects. Since this sweeping algorithm is slower when the heap occupancy is high, we also discuss how to avoid this slowdown by using an adaptive algorithm. Copyright © 2004 John Wiley & Sons, Ltd.

Java supports the monitor construct for language-level synchronization in the context of multi-threading. This paper introduces the lightweight monitor, an efficient user-level monitor implementation. The lightweight monitor is useful for single-threaded Java programs as well as for multi-threaded Java programs with little lock contention. A 32-bit lock is embedded in each object for efficient lock access while other monitor data structures are managed using a hash table. We highly optimized the lock manipulation code, which is translated and inlined by a just-in-time (JIT) compiler. In the most probable cases, only nine SPARC instructions are spent for lock acquisition and five instructions are spent for lock release. Our experimental results indicate that the lightweight monitor is faster than the monitor implementation in the SUN JDK 1.2 RC1 by up to 21 times in the absence of lock contention and by up to seven times in the presence of lock contention. Copyright © 2004 John Wiley & Sons, Ltd.

Abstract Java uses exceptions to provide elegant error handling capabilities during program execution. However, the presence of exception handlers complicates the job of the just‐in‐time (JIT) compiler, while exceptions are rarely used in most programs. This paper describes two techniques for reducing such complications. First, we delay the translation of an exception handler until the exception really occurs. This on‐demand translation of exception handlers allows more optimizations when translating the main flow, without being hindered by constraints caused by the exception flows. Secondly, for those exceptions that are actually thrown during program execution we insert exception‐type check code and a direct branch to the translated exception handlers. This exception handler prediction is motivated by an observation that frequently thrown exceptions are likely to be handled by the same exception handlers, so this will eliminate the exception processing overhead of the Java virtual machine. Our experiments indicate that the code quality of the main flow is no longer affected by the presence of exception handlers. Also, frequently thrown exceptions can be efficiently handled by the exception handler prediction. Copyright © 2004 John Wiley & Sons, Ltd.

Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike aggressive coalescing , which coalesces any pair of noninterfering copy-related nodes, conservative coalescing or iterated coalescing perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities for coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This article proposes a new heuristic called optimistic coalescing which optimistically performs aggressive coalescing, thus exploiting the positive impact of coalescing aggressively, but when a coalesced node is to be spilled, it is split back into separate nodes. Since there is a better chance of coloring one of those splits, we can reduce the overall spill amount.

Software pipelining increases the loop execution throughput by overlapping the execution of successive iterations in a pipelined fashion. For loops with control flows, however, software pipelining is not straightforward because we need to consider the overlap of more than one execution path. Modulo scheduling simply transforms them into straightline loops through if-conversion which, in effect, achieves a fixed, worst-case initiation interval (/spl par/) among all paths. On the other hand, all-path pipelining (APP) and enhanced pipeline scheduling (EPS) can achieve a variable /spl par/ depending on the path that is taken at execution time. Unfortunately, APP concentrates only on the overlap within the same path, entirely losing the overlap between different paths, whereas EPS attempts to overlap all paths together, failing to produce a tight schedule for each individual path, especially when resource constraints are tight. In this paper, we propose a new approach to EPS called split-path EPS (SP-EPS), which first splits each individual path via tail duplication and then performs EPS in a way to guarantee a tight schedule for each path, while producing a competitive cross-path schedule. We also extend SP-EPS to outer loops such that frequent paths that bypass the inner loop are split and then scheduled by SP-EPS. Our experimental results on nontrivial integer benchmarks show that SP-EPS can achieve as much as a geometric mean of 10 percent speedup over EPS when innermost loops are scheduled by SP-EPS, while it can achieve a geometric mean of 11.9 percent speedup when outer loops are also scheduled by SP-EPS.

Software pipelining is widely used as a compiler optimization technique to achieve high performance in machines that exploit instruction -level parallelism. However, surprisingly, there have been few theoretical or empirical results on optimal software pipelining of loops with control flows. In this paper, we present three new contributions for this under-investigated problem. First, we propose a necessary and sufficient condition for a loop with control flows to have an optimally software-pipelined program. We also present a decision procedure to compute the condition. Second, we present two software pipelining algorithms. The first algorithm computes an optimal solution for every loop satisfying the condition, but may run in exponential time. The second algorithm computes optimal solutions efficiently for most (but not all) loops satisfying the condition. Third, we present experimental results which strongly indicate that achieving the optimality in the software-pipelined programs is a viable goal in practice with realistic hardware support.

Enhanced pipeline scheduling (EPS) is a software pipelining technique which can achieve a variable initiation interval (II) for loops with control flow via its code motion pipelining. EPS, however, leaves behind many renaming copy instructions that cannot be coalesced due to interferences. These copies take resources and, more seriously, they may cause a stall if they rename a multilatency instruction whose latency is longer than the II aimed for by EPS. This paper proposes a code transformation technique based on loop unrolling which makes those copies coalescible. Two unique features of the technique are its method of determining the precise unroll amount, based on an idea of extended live ranges, and its insertion of special bookkeeping copies at loop exits. The proposed technique enables EPS to avoid a serious slowdown from latency handling and resource pressure, while keeping its variable II and other advantages. In fact, renaming through copies, followed by unroll-based copy elimination, is EPS's solution to the cross-iteration register overwrite problem in software pipelining. It works for loops with arbitrary control flow that EPS must deal with, as well as for straightline loops. Our empirical study performed on a VLIW testbed with a two-cycle load latency shows that 86 percent of the otherwise uncoalescible copies in innermost loops become coalescible when unrolled 2.2 times on average. In addition, it is demonstrated that the unroll amount obtained is precise and the most efficient. The unrolled version of the VLIW code includes fewer no-op VLIW caused by stalls, improving the performance by a geometric mean of 18 percent on a 16-ALU machine.

Aggressive instruction scheduling leaves behind many renaming copy instructions that cannot be coalesced due to interferences. These copies take resources, and more seriously, they may cause a stall if they are generated for renaming of multi-latency instructions. This paper proposes a code transformation technique based on loop unrolling which makes those copies coalescible. Two unique features of the technique are its method of determining the precise unroll amount based on an idea of extended live range, and its insertion of special bookkeeping copies at loop exits. In fact, the technique provides a more general and simpler solution for the cross-iteration register overwrite problem in software pipelining which works for loops with control flows as well as for straight-line loops. In addition, it is applicable to other optimizations including path length reduction and redundant subscripted reference elimination.

Dynamic memory allocation is an important part of modern programming languages. It is important that it be done fast without wasting too much memory. Memory allocation using lazy fits is introduced, where pointer increments, which is very fast, is used as the primary allocation method and where conventional fits such as best fit or first fit are used as backup. Some experimental results showing how lazy fits might perform are shown, and shows that the approach has the potential to be useful in actual systems.

Mark and sweep garbage collectors are known for using time proportional to the heap size when sweeping memory, since all objects in the heap, regardless of whether they are live or not, must be visited in order to reclaim the memory occupied by dead objects. This paper introduces a sweeping method which traverses only the live objects, so that sweeping can be done in time dependent only on the number of live objects in the heap.

Software pipelining increases the loop execution throughput by overlapping the execution of successive iterations in a pipelined fashion. For loops with control flows, software pipelining is not straightforward because we need to consider the overlap of more than one execution path. Modulo scheduling simply transforms them into straight-line loops through if-conversion which, in effect, achieves a fixed, worst-case initiation interval (II) among all paths. All-path pipelining (APP) and enhanced pipeline scheduling (EPS) can achieve a variable II depending on the path that is followed through the loop at execution time. Unfortunately, APP concentrates only on the overlap within the same path, entirely losing the overlap between different paths, whereas EPS attempts to overlap all future paths together, failing to produce a tight schedule for each individual path. In this paper, we propose a new approach to EPS which splits each individual path in the loop via tail duplication, and performs EPS in a way to guarantee a tight schedule within the same path, while producing a comparable cross-path schedule. Our experimental results indicate that the proposed technique can achieve as much as a geometric mean of 7% performance improvement on non-trivial integer benchmarks.

Modern single-CPU microprocessors exploit instruction-level parallelism (ILP) by deriving their performance advantage mainly from parallel execution of ALU and memory instructions within a single clock cycle. This performance advantage obtained by exploiting data ILP is severely offset by sequential execution of conditional branches, especially in branch-intensive non-numerical code. Consequently, branch ILP must also be exploited by executing branches and data instructions in parallel. This requires compilation support for scheduling branches as well as architectural support for executing branches and data instructions in the same cycle. This paper performs a comprehensive empirical study aimed at evaluating the performance impact of exploiting branch ILP using a representation of ILP code called tree representation, which has been proposed by Nicolau [A. Nicolau (1985), Technical Report TR-85-678, Cornell University, Ithaca, NY] and Ebcioğlu to exploit branch ILP in the most generalized form. Our results indicate that exploiting branch ILP can enhance performance substantially (i.e., as much as a geometric mean of speedup 4.5 in the 16-ALU machine, compared to the base speedup 3.0) and that the performance benefit comes not only from the intended parallel execution but from the decrease of useless speculative execution due to earlier scheduling of branches.

In order to fully exploit instruction-level parallelism (ILP) in non-numerical code, we must exploit branch ILP as well as data ILP.Exploiting branch ILP requires architectural support for executing branches and data instructions in parallel, and the compiler needs to schedule conditional branches.As a VLIW architecture that exploits branch ILP in the most generalized form, we have proposed the tree VLIW architecture [ 1], which exhibits significant performance advantage when combined with appropriate scheduling techniques [2].This paper analyzes the performance advantage, characterizing the performance impact of the tree VLIW architecture.We also provide pertinent insights into its two architectural features (generalized multi-way branching and conditional execution) and describe implementation details of the tree VLIW machine.Our analysis indicates that the performance benefit of the tree VLIW architecture comes not only from the intended branch ILP but from the improvement of data ILP caused by the decrease of useless speculative execution.

The performance of Very Long Instruction Word (VLIW) microprocessors depends on the close cooperation between the compiler and the architecture. This paper evaluates a set of important compilation techniques and related architectural features for VLIW machines. The evaluation is performed on a SPARC-based VLIW testbed where gcc-generated optimized SPARC code is scheduled into high-performance VLIW code. As a base scheduling compiler, we experiment with three core scheduling techniques including enhanced pipeline scheduling, all-path speculation, and renaming. We analyze the characteristics of the useful and useless ALUs in each cycle to see how many of those ALUs execute non-speculative operations, speculative operations, and copies, respectively. Then, we evaluate the following compilation techniques: software pipelining, loop unrolling, non-greedy enhanced pipeline scheduling, profile-based all-path speculation, trace-based speculation, renaming, restricted speculative loads, and memory disambiguation. Since we experiment on a uniform testbed based on a detailed analysis of ALUs, our evaluation provides an useful insight on the performance impact of these techniques.

Instruction-level parallelism (ILP) in nonnumerical code is regarded as scarce and hard to exploit due to its irregularity. In this article, we introduce a new code-scheduling technique for irregular ILP called “selective scheduling” which can be used as a component for superscalar and VLIW compilers. Selective scheduling can compute a wide set of independent operations acrossallexecution paths based on renaming and forward-substitution and can compute available operations across loop iterations if combined with software pipelining. This scheduling approach has better heuristics for determining the usefulness of moving one operation versus moving another and can successfully find useful code motions without resorting to branch profiling. The compile-time overhead of selective scheduling is low due to its incremental computation technique and its controlled code duplication. We parallelized the SPEC integer benchmarks and five AIX utilities without using branch probabilities. The experiments indicate that a fivefold speedup is achievable on realistic resources with a reasonable overhead in compilation time and code expansion and that a solid speedup increase is also obtainable on machines with fewer resources. These results improve previously known characteristics of irregular ILP.

VLIW processors use multiway branch instructions to achieve high-speed, parallel evaluation of control structures. This paper introduces a new multiway branch mechanism that allows constant-time branch-target resolution based on an arbitrary condition tree. The unique feature of this mechanism is its target selection unit, which yields a branch-target based on a set of condition bit values and a condition tree description. A representation of condition trees that results in a compact target selection unit is described, and the logic diagram of a target selection unit that provides a four-way branching is shown. Our experimental results on nontrivial integer benchmarks indicate that the proposed multiway branch unit can improve the performance of VLIW machines substantially (i.e., as much as a geometric mean of 35%), compared to using the conventional two-way branching.>

An accurate and safe estimation of a task's worst case execution time (WCET) is crucial for reasoning about the timing properties of real time systems. In RISC processors, the execution time of a program construct (e.g., a statement) is affected by various factors such as cache hits/misses and pipeline hazards, and these factors impose serious problems in analyzing the WCETs of tasks. To analyze the timing effects of RISC's pipelined execution and cache memory, we propose extensions to the original timing schema where the timing information associated with each program construct is a simple time bound. In our approach, associated with each program construct is worst case timing abstraction, (WCTA), which contains detailed timing information of every execution path that might be the worst case execution path of the program construct. This extension leads to a revised timing schema that is similar to the original timing schema except that concatenation and pruning operations on WCTAs are newly defined to replace the add and max operations on time bounds in the original timing schema. Our revised timing schema accurately accounts for the timing effects of pipelined execution and cache memory not only within but also across program constructs. The paper also reports on preliminary results of WCET analysis for a RISC processor. Our results show that tight WCET bounds (within a maximum of about 30% overestimation) can be obtained by using the revised timing schema approach.>

Sequential execution of conditional branches in non-numerical code limits the exploitation of instruction-level parallelism (ILP). In order to cope with this limiation, exploitation of parallelism must be extended to concurrent execution of data and branches in a single cycle.

Instruction-level parallelism in non-numerical code character as leading to small speeduo (as little) due to its irregularity. Recently, we have developed a new static scheduling algorithm called selective scheduling which can be used as a component of VLIW and superscalar compilers to exploit the irregular parallelism.

Compiler-controlled speculative execution has been shown to be effective in increasing the available instruction level parallelism (ILP) found in non-numeric programs. An important problem associated with compiler-controlled speculative execution is to accurately report and handle exceptions caused by speculatively executed instructions. Previous solutions to this problem incur either excessive hardware overhead or significant register pressure. The paper introduces a new architectural scheme referred to as write-back suppression. This scheme systematically suppresses register file updates for subsequent speculative instructions after an exception condition is detected for a speculatively executed instruction. The authors show that with a modest amount of hardware, write-back suppression supports accurate reporting and handling of exceptions for compiler-controlled speculative execution with minimal additional register pressure. Experiments based on a prototype compiler implementation and hardware simulation indicate that ensuring accurate handling of exceptions with write-back suppression incurs little run-time performance overhead.>