This paper deals with a job-shop scheduling problem with complicated constraints. In the problem precedence relations exist nor only among operations but also among jobs. Furthermore, this production system has several types of single function machines and a type of multifunction machine, and the number of machines available is plural for the respective types. Therefore selection of the machine is necessary for executing each operation. An autonomous decentralized scheduling algorithm is proposed to obtain a suboptimal solution of this problem. The effectiveness of the proposed algorithm is investigated by examining numerical results. Moreover, the algorithm is also applied to a rescheduling problem in the case where a machine breaks down.

Many studies have investigated performance improvement through exploiting instruction-level parallelism (ILP) with a particular architecture. Unfortunately, these studies indicate performance improvement using the number of cycles that are required to execute a program, but do not quantitatively estimate the penalty imposed on the cycle time from the architecture. Since the performance of a microprocessor must be measured by its execution time, a cycle time evaluation is required as well as a cycle count speedup evaluation. Currently, superscalar machines are widely accepted as the machines which achieve the highest performance. On the other hand, because of hardware simplicity and instruction scheduling sophistication, there is a perception that the next generation of microprocessors will be implemented with a VLIW architecture. A simple VLIW machine, however, has a serious weakness regarding speculative execution. Thus, it is a question whether a simple VLIW machine really outperforms a superscalar machine. We recently proposed a mechanism called predicating that supports speculative execution for the VLIW machine, and showed a significant cycle count speedup over a scalar machine. Although the mechanism is simple, it is unknown how much it imposes a penalty on the cycle time, and how much the performance is improved as a result. This paper evaluates both the cycle count speedup and the cycle time for three ILP machines: a superscalar machine, a simple VLIW machine, and the VLIW machine with predicating. The evaluation results show that the simple VLIW machine slightly outperforms the superscalar machine, while the VLIW machine with predicating achieves a significant speedup of 1.41x over the superscalar machine.

Speculative execution is execution of instructions before it is known whether these instructions should be executed. Compiler-based speculative execution has the potential to achieve both a high instruction per cycle rate and high clock rate. Pure compiler-based approaches, however, have greatly limited instruction scheduling due to a limited ability to handle side effects of speculative execution. Significant performance improvement is, thus, difficult in non-numerical applications. This paper proposes a new architectural mechanism, called predicating, which provides unconstrained speculative execution. Predicating removes restrictions which limit the compiler's ability to schedule instructions. Through our hardware support, the compiler is allowed to move instructions past multiple basic block boundaries from any succeeding control path. Predicating buffers the side effects of speculative execution with its predicate, and the buffered predicate efficiently commits or squashes the side effects. The mechanism also provides a speculative exception handling scheme. The scheme, called the future condition, properly postpones speculative exceptions and efficiently restarts the process. We show that our mechanism can be implemented through a modest amount of hardware with little complexity. The evaluation results show that our mechanism significantly improves performance, and achieves a 2.45x speedup over scalar machines.

Parallel instruction issue is essential for performance improvement in current microprocessor designs. Just extra function units are, however, little beneficial in non-numerical applications since control dependence severely limits exploitation of instruction-level parallelism (ILP) and frequent branches consume ILP due to its long latency. Boosting is an interesting technique to reduce control dependence. It allows general speculative execution with little cycle time penalty. From the cost/performance point of view, we propose the efficient implementation of boosting, which requires the small support hardware and maximizes performance gain from boosting in the limited hardware. We also propose a new branch scheme to reduce the branch penalty which has a particularly big performance impact in a parallel issue machine. Our scheme fetches from both directions of the branch with small hardware cost through integration of a code movement and hardware support. We evaluate our schemes and find that they significantly contribute to performance improvement.>