We present a fast loop parallelization heuristic that assigns separate invocations of a loop to different processors. If the loop contains data dependences between iterations, later iterations can be delayed while awaiting a result computed in an earlier iteration. In this paper we study a scheduling problem, called the Delay Problem, that approximates the problem of minimizing the delay in the start time of loops with loop-carried dependences. Our major result is a fast (O(n log 2 n)) time algorithm for the case where the precedence constraints are a forest of in-trees or a forest of out-trees. Since most graphs for the Delay Problem that arise in practice are sparse and consist of such a forest with possibly a few additional edges, this is an important case. We prove that the Delay Problem becomes NP-Complete when the precedence constraints are a set of arbitrary trees. We also prove that the Delay Problem becomes NP-Complete for independent chains when it is generalized to allow either non-unit execution times or release times and deadlines.
Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing ρ for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. Choosing a good routing corresponds to bounding the diameter of the surviving route graph R(G,ρ)/F, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. We prove a number of results concerning the diameter of surviving route graphs. We show that if ρ is a minimal length routing, then the diameter of R(G,ρ)/F can be on the order of the number of nodes of G, even if F consists of only a single node. However, if G is the n-dimensional cube, the diameter of R(G,ρ)/F≤3 for any minimal length routing ρ and any set of faults F with |F|
We present an algorithm for analyzing deadlock and for constructing sequentializations of a class of communicating sequential processes. The algorithm may be used for deadlock detection in parallel and distributed programs at compile time, or for debugging purposes at run time. The algorithm generates a data structure we call the flow graph, which contains all you need to know about the communications between the processes. If the algorithm is used only for debugging, it is not necessary to retain a copy of the flow graph. Both static deadlock analysis and trace generation are linear in the size of the (minimum) flow graph we construct.
An instruction or a set of instructions can be considered time critical if their execution is required to free up a resource. Time critical instructions might be used to make shared resources such as registers more quickly available for reuse; or they might be used for real time computations, portions of which are critical for the operation of some piece of equipment. In this paper we present a polynomial time algorithm for optimally scheduling instructions with or without time critical constraints on RISC machines such as the IBM 801, the Berkeley RISC machine, and the HP Precision Architecture. We also show that in the absence of time critical constraints, the greedy algorithm always produces a schedule for a target machine with multiple identical pipelines that has a length less than twice that of an optimal schedule. The behavior of the greedy algorithm is of interest because, as we show, the instruction scheduling problem becomes NP-hard for arbitrary length pipelines, even when the basic block of code being input consists of only several independent streams of straight-line code, and there are no time-critical constraints. Finally, we present the first correct proofs that the problem becomes NP-hard even for small pipelines, no time-critical constraints, and input of several independent streams of straight-line code if there is only a single register or if there is a bus constraint.
Purpose Sustained access to efficient electricity plays an essential role in improving living conditions of people and contributes to the economic development of the nation as a whole. Volta River Authority (VRA) mainly manages the generation plants (hydropower sources and thermal plants) alongside independent power producers (IPPs). Power generation in the country has been influenced by myriads of factors. Thus, the purpose of this study is to assess the key risk factors affecting renewable energy of IPPs set-up project in Ghana. Design/methodology/approach Quantitative approach was adopted for the study. Empirical investigation was carried out using the survey approach. The likelihood of occurrence of the risk and the degree of impact of same motivated the use of risk significance index to analyze the data and make deductions from the results. Findings From the study, three key risk factors have high level of severity, which include long and complex procedures for authorization of project activities, stability of the policy environment and ease of obtaining rights to land. These risks could be found in the business/strategic risks and policy/regulatory risks categories, respectively. A total of 25 key risk factors had moderate level of severity and 12 key risk factors have low level of severity on renewable energy IPP set up projects. Practical implications Top-ranked risk factors require maximum attention. The identified risks should be alleviated with strategies to reduce levels of severity by targeting either the likelihood of occurrence or the level of impact. This will serve as a catalyze to promoting renewable energy IPP set-up projects in Ghana. Originality/value Key contribution of the paper to the body of knowledge is demonstrated by the empirical evidence of the risks IPPs are likely to encounter in setting up renewable energy plants in Ghana. The distinctive attribute of this study is further demonstrated by the fact that it focused on the set-up stage, which is a critical stage in the renewable energy provision value chain.
Discussion of the merits and shortcomings of affirmative action (AA) has raged at all levels and in many forums and has been the concern of many policymakers, including President Clinton. Notably absent from the discussion is the perception of AA, and the effect of the angry backlash on women and minorities. Recently, the question of whether women enjoy an “unfair advantage” was posted electronically on Systers, a private organization of over 1,800 professional women in the male-dominated field of computing. The 42 responses contained strong personal stories from women at every level of professional growth who had all dealt with the issues of gender bias and AA at each step of the way.
