Loop Shifting for Loop Compaction

The idea of decomposed software pipelining is to decouple the software pipelining problem into a cyclic scheduling problem without resource constraints and an acyclic scheduling problem with resource constraints. In terms of loop transformation and code motion, the technique can be formulated as a combination of loop shifting and loop compaction. Loop shifting amounts to moving statements between iterations thereby changing some loop independent dependences into loop carried dependences and vice versa. Then, loop compaction schedules the body of the loop considering only loop independent dependences, but taking into account the details of the target architecture. In this paper, we show how loop shifting can be optimized so as to minimize both the length of the critical path and the number of dependences for loop compaction. The first problem is well-known and can be solved by an algorithm due to Leiserson and Saxe. We show that the second optimization (and the combination with the first one) is also polynomially solvable with a fast graph algorithm, variant of minimum-cost flow algorithms. Finally, we analyze the improvements obtained on loop compaction by experiments on random graphs.     

FAST: acceleration from theory to practice

Fast acceleration of symbolic transition systems (Fast) is a tool for the analysis of systems manipulating unbounded integer variables. We check safety properties by computing the reachability set of the system under study. Even if this reachability set is not necessarily recursive, we use innovative techniques, namely symbolic representation, acceleration and circuit selection, to increase convergence. Fast has proved to perform very well on case studies. This paper describes the tool, from the underlying theory to the architecture choices. Finally, Fast capabilities are compared with those of other tools. A range of case studies from the literature is investigated. This paper is mainly based on results presented at CAV 2003, TACAS 2004 and ATVA 2005.     

Snap-stabilization and PIF in tree networks

The contribution of this paper is threefold. First, we present the paradigm of snap-stabilization. A snap- stabilizing protocol guarantees that, starting from an arbitrary system configuration, the protocol always behaves according to its specification. So, a snap-stabilizing protocol is a time optimal self-stabilizing protocol (because it stabilizes in 0 rounds). Second, we propose a new Propagation of Information with Feedback (PIF) cycle, called Propagation of Information with Feedback and Cleaning (). We show three different implementations of this new PIF. The first one is a basic cycle which is inherently snap-stabilizing. However, the first PIF cycle can be delayed O(h ²) rounds (where h is the height of the tree) due to some undesirable local states. The second algorithm improves the worst delay of the basic algorithm from O(h ²) to 1 round. The state requirement for the above two algorithms is 3 states per processor, except for the root and leaf processors that use only 2 states. Also, they work on oriented trees. We then propose a third snap-stabilizing PIF algorithm on un-oriented tree networks. The state requirement of the third algorithm depends on the degree of the processors, and the delay is at most h rounds. Next, we analyze the maximum waiting time before a PIF cycle can be initiated whether the PIF cycle is infinitely and sequentially repeated or launch as an isolated PIF cycle. The analysis is made for both oriented and un-oriented trees. We show or conjecture that the two best of the above algorithms produce optimal waiting time. Finally, we compute the minimal number of states the processors require to implement a single PIF cycle, and show that both algorithms for oriented trees are also (in addition to being time optimal) optimal in terms of the number of states. WARNING: The concept of snap-stabilization was first introduced in [12]. The concept evolved over the last eight years. We take this evolution in consideration in this paper, which includes the early results published in [10] and [12]. In particular, infinite repetition of computation cycles is a requirement of self-stabilizing systems. This is not required in snap-stabilization because snap-stabilization ensures that the first completed computation cycle is executed according to the specification of the problem. The correctness proofs conform to this basic property.     

A local approach to concept generation

Generating concepts defined by a binary relation between a set of properties and a set of objects is one of the important current problems encountered in Data Mining and Knowledge Discovery in Databases. We present a new algorithmic process which computes all the concepts, without requiring an exponential-size data structure, and with a good worst-time complexity analysis, which makes it competitive with the best existing algorithms for this problem. Our algorithm can be used to compute the edges of the lattice as well at no extra cost.      

On the use of analytical expressions for the voltage distribution to analyze intracellular recordings

Different analytical expressions for the membrane potential distribution of membranes subject to synaptic noise have been proposed and can be very helpful in analyzing experimental data. However, all of these expressions are either approximations or limit cases, and it is not clear how they compare and which expression should be used in a given situation. In this note, we provide a comparison of the different approximations available, with an aim of delineating which expression is most suitable for analyzing experimental data.     

An empirical analysis of the determinants of 3G adoption in China

The main aim of this study is to examine the factors that affect Chinese consumers’ intention to adopt 3G. This study has extended the Technology Acceptance Model (TAM) by incorporating the determinants of perceived usefulness, cost, trust, and demographic profiles of Chinese consumers. Data is collected from Chinese consumers via self-administered questionnaire. Structural equation modeling was applied to examine the research model proposed. Our result showed that social influence, service quality and perceived ease of use have a direct and significant relationship with perceived usefulness of 3G, and this in turn affects the consumers’ decision to adopt 3G. Contrary to existing TAM research, perceived ease of use was not found to have a direct and significant influence with Chinese consumers’ intention to adopt 3G. Our study also revealed that those with higher educational level are more likely to adopt 3G. Based on the findings, this research is able to propose several practical recommendations to 3G providers in China, such as enhancing the variety of services provided through collaborations with mobile software and content developers. Furthermore, 3G providers can focus on promoting 3G through services such as “Friends and Family” packages as Chinese consumers’ 3G adoption decisions is influenced by their social network. In terms of theoretical contributions, this study has answered many calls from past researchers to investigate the determinants of perceived usefulness. This research was also conducted in China, which is one of the largest telecommunication markets in the world.     

Reducing aliasing in images: a PDE-based diffusion revisited

In this paper, we introduce a new diffusion algorithm that can be used for reducing aliasing on both step edges and lines. It derives from the diffusion model of Perona and Malik, and works as an adaptive level-curve method in which diffusion is carried out in the normal direction of the gradient for step edges, while the eigenvalues of the Hessian matrix are used for lines. To get sharp images, we use high-pass filters to preserve as much as possible the high frequency content while diffusing. Experimental tests using grayscale and colour images show that our algorithm efficiently reduces aliasing.     

Stereoelective polymerization of β-butyrolactone

Racemic β-butyrolactone was polymerized using chiral initiators obtained from the reaction of organometallic derivatives (ZnEt₂, CdMe₂, AlEt₃) with R(−) 3,3 dimethyl-1,2 butanediol. With the zinc initiator, R(+) enantiomer is preferentially incorporated in the polymer chain with a stereoelectivity ratio r_R equal to 1.6. Crude polymer was fractionated into a crystalline, predominantly isotactic, part and an amorphous heterotactic part, both optically active. Sites of different stereospecificities, present in the initiator, are all active for the stereoelective polymerization. With the cadmium initiator, S(−) enantiomer is preferentially polymerized (r_s = 1.01), extending homosteric-antisteric rules previously established for thiiranes. Aluminium initiator leads to an homosteric process (r_R = 1.1). Chiroptical properties (o.r.d. and c.d.) of polymers prepared with zinc initiator show a predominance of R-configurational units, indicating that ring-opening occurs by O-acyl cleavage with retention of configuration.     

BiNem® manufacturing process for mass production

Abstract— As the need for high‐resolution ultra‐low‐power bistable displays grows, it is important to rapidly implement the mass‐production manufacturing of BiNem® LCDs. The cost‐effective approach for BiNem® manufacturing is based on using STN manufacturing process technologies since BiNem® and STN displays have a similar internal structure. The key differences between BiNem® and STN displays from a manufacturing point of view will be discussed. We show that industrial STN manufacturing equipment can be used to produce BiNem® LCDs at competitive costs. Reflective e‐book display modules with VGA resolution are produced in the pilot‐production series.     

Inferential Queueing and Speculative Push

Communication latencies within critical sections constitute a major bottleneck in some classes of emerging parallel workloads. In this paper, we argue for the use of two mechanisms to reduce these communication latencies: Inferentially Queued locks (IQLs) and Speculative Push (SP). With IQLs, the processor infers the existence, and limits, of a critical section from the use of synchronization instructions and joins a queue of lock requestors, reducing synchronization delay. The SP mechanism extracts information about program structure by observing IQLs. SP allows the cache controller, responding to a request for a cache line that likely includes a lock variable, to predict the data sets the requestor will modify within the associated critical section. The controller then pushes these lines from its own cache to the target cache, as well as writing them to memory. Overlapping the protected data transfer with that of the lock can substantially reduce the communication latencies within critical sections. By pushing data in exclusive state, the mechanism can collapse a read-modify-write sequences within a critical section into a single local cache access. The write-back to memory allows the receiving cache to ignore the push. Neither mechanism requires any programmer or compiler support nor any instruction set changes. Our experiments demonstrate that IQLs and SP can improve performance of applications employing frequent synchronization.