Indian Institute of Science Bangalore
etd@IISc Electronic Theses and Dissertations at Indian Institute of ScienceNot a member yet
6204 research outputs found
Sort by
A Broadcast Cube-Based Multiprocessor Architecture for Solving Partial Differential Equations
No full textA large number of mathematical models in engineering and physical sciences employ Partial Differential Equations (PDEs). The sheer number of operations required in numerically integrating PDEs in these applications has motivated the search for faster methods of computing. The conventional uniprocessor computers are often unable to fulfill the performance requirements for these computation intensive problems. In this dissertation, a cost-effective message-based multiprocessor system which we call the Broadcast Cube System (BCS) has been proposed for solving important computation intensive problems such as, systems of linear algebraic equations and PDEs. A simulator for performance evaluation of parallel algorithms to be executed on the BCS has been implemented. A strategy (task assignment . algorithm) for assigning program tasks with precedence and communication constraints to the Processing Elements (PEs) in the BCS has been developed and its effectiveness demonstrated. This task assignment algorithm has been shown to produce optimal assignments for PDE problems. Optimal partitioning of the problems, solving systems of linear algebraic equations and PDEs, into tasks and their assignment to the PEs in the BCS have been given. Efficient parallel algorithms for solving these problems on the BCS have been designed. The performance of the parallel algorithms has been evaluated by both analytical and simulation methods. The results indicate that the BCS is highly effective in solving systems of linear algebraic equations and PDEs. The performance of these algorithms on the BCS has also been compared with that of their implementations on popular hypercube machines. The results show that the performance of the BCS is better than that of the hypercubes for linear algebraic equations and compares very well for PDEs, with a modest number of PEs despite the constant PE connectivity of three in the BCS. Finally, the effectiveness of the BCS in solving non-linear PDEs occurring in two important practical problems, (i) heat transfer and fluid flow simulation and (ii) global weather modeling, has been demonstrated.Indian Institute of Scienc
Influence of Lot Sizing on Lead Time Error Costs in M.R.P. Systems- a Computer Simulation Study
No full textTiming of ordering of inventory items is of very great importance in Materials Requirement Planning. Uncertainties in timing can have an adverse effect on the system performance. Most often the lead time variation contribute to timing uncertainties; and their effects are reflected in added costs.
Lead time error effects are investigated in this thesis. The study attempts to estimate the effects through some relevant costs, and their variations across the lot sizing rules.
The hypotheses for this study are 1) Between any two lot sizing rules, there will be a significant difference in error coats due to combined effect of purchased lead time error and manufacturing lead time errors; 2) Relative cost performance of lot sizing rules in MRP is influenced by the lead time errors; 3) There will be a difference in error cost between lot for l o t rule and least total cost rule even with single source of lead time variation.
To carry out the study a MRP programme was developed, in FORTRAN 77 with provisions to include the lot sizing rules while exploding the structure. The lot sizing rules used in the study are Lot for Lot, Silver and Meal heuristics, Wagner-Whitin algorithm, Least total cost, Least unit cost and Part Period balancing.
A simulation model is developed using GPSS/PC, to test the hypotheses. An hypothetical production situation with three end items, each with a different product structure is designed. In addition, a master production schedule and a job shop are also structured. Appropriate distributions are assumed for both manufacturing lead times and purchase lead times. These provide the stochastic variables in the simulation experiments.
A series of experiments were carried out with the model to investigate into the variations of costs amongst lot sizing rules. Results of the simulation experiments prove that there are costs associated with lead time errors in MRP. These error costs vary significantly with different lot sizing rules.
It is also found that the resultant error costs vary significantly even with a single source of lead time variation. Least unit cost rule gives the beat performance having least error costs. Lot for Lot rule has shown the worst performance amongst the lot sizing rules considered. Other interesting results have emerged out of the study
Hierarchical Data Structures for Pattern Recognition
No full textPattern recognition is an important area with potential applications in computer vision, Speech understanding, knowledge engineering, bio-medical data classification, earth sciences, life sciences, economics, psychology, linguistics, etc. Clustering is an unsupervised classification process corning under the area of pattern recognition. There are two types of clustering approaches:
1) Non-hierarchical methods 2) Hierarchical methods. Non-hierarchical algorithms are iterative in nature and. perform well in the context of isotropic clusters. Time-complexity of these algorithms is order of (0 (n) ) and above, Hierarchical agglomerative algorithms, on the other hand, are effective when clusters are non-isotropic. The single linkage method of hierarchical category produces a dendrogram which corresponds to the minimal spanning tree, conventional approaches are time consuming requiring O (n2 ) computational time.
In this thesis we propose an intelligent partitioning scheme for generating the minimal spanning tree in the co-ordinate space. This is computationally elegant as it avoids the computation of similarity between many pairs of samples me minimal spanning tree generated can be used to produce C disjoint clusters by breaking the (C-1) longest edges in the tree.
A systolic architecture has been proposed to increase the speed of the algorithm further. Simulation study has been conducted and the corresponding results are reported. The simulation package has been developed on DEC-1090 in Pascal. It is observed based on the simulation study that the parallel implementation reduces the time enormously. The number of processors required for the parallel implementation is a constant making the approach more attractive.
Texture analysis and synthesis has been extensively studied in the context of computer vision, Two important approaches which have been studied extensively by researchers earlier are statistical and structural approaches, Texture is understood to be a periodic pattern with primitive sub patterns repeating in a particular fashion. This has been used to characterize texture with the help of the hierarchical data structure, tree. It is convenient to use a tree data structure as, along with the operations like merging, splitting, deleting a node, adding a node, etc, .it would be useful to handle a periodic pattern. Various functions like angular second moment, correlation etc, which are used to characterize texture have been translated into the new language of hierarchical data structure
Implementation Of Database Security Features Using Bit Matrices
No full textInformation security is of utmost concern in a multiuser environment. The importance of security is felt much more with the widespread use of distributed database. Information is by itself a critical resource of an enterprise and thus the successful operation of an enterprise demands that data be made accessible only by authorized users and that the data be made to reflect the state of the enterprise.
Since many databases are online, accessed by multiple users concurrently, special mechanisms are needed to insure integrity and security of relevant information, This thesis describes a model for computer database security that supports a wide variety of security policies.
The terms security policies and security mechanism are presented in Chapter I. The interrelated topics of security and integrity are discussed in some detail. The importance and means of insuring security of information is also presented in this chapter.
In Chapter 2, the work done In the field of Computer Security and related topic has been presented. In general computer security models could be classified broadly under the two categories.
(1) Models based on Access Control Matrix and
(2) Models based on Information Flow Control.
The development of the models baaed on the above two schemes as also the policies supported by some of the schemes are presented in this chapter.
A brief description of the work carried out in database security as aim the definition of related terns are given in Chapter 3. The interrelationship between the operating system security and database security is also presented in this chapter. In general the database security mechanism depends on the existing operating system. The database security mechanism are thus only as strong as the underlying operating system on which it is developed. The various schemes used for implementing database security such as access controller and capability lists are described in this chapter.
In Chapter 4, a model for database security has been described. The model provides for:
(a) Delegation of access rights by a user and
(b) Revocation of access rights previously granted by a user.
In addition, algorithms for enforcing context dependent and content dependent rules are provided in this cheer. The context-dependent rules are stored in the form of elements of a bit matrix. Context-dependent rules could then be enforced by suitably manipulating the bit matrix and interpreting the value of me elements of the matrix, The major advantage of representing the rules using bit matrices is that the matrix itself could be maintalnet3 in main memory. The time taken to examine if a user is authorized to access an object is drastically reduced because of the reduced time required to inspect main memory. The method presented in this chapter, in addition to reducing the time requirement for enforcing security also presents a method for enforcing decentralized authorization control, a facility that is useful in a distributed database environment.
Chapter 5 describes a simulation method that is useful for comparing the various security schemes. The tasks involved in the simulation are –
1. Creation of an arrival (job).
2. Placing the incoming job either in the wait queue or in the run state depending on the type of access needed for: the object.
3. Checking that the user on whose behalf the job is being executed is authorized to access the object in the mode requested.
4. Checking for the successful completion of the job and termination of the job.
5. Collection of important parameters such as number of jobs processed, average connect time.
Simulation was carried out for timing both the access controller scheme and bit matrix scheme, The results of the simulation run bear the fact that the bit matrix scheme provides a faster method Six types of access were assumed to be permissible, three of the access types requiring shared lock and the rest requiring exclusive locks on the objects concerned, In addition the only type of operation allowed was assumed to be for accessing the objects.
It is be noted that the time taken to check for security violation is but one of the factors for rating the security system. In general, various other factors such as cost of implementing the security system, the flexibility that offers enforcing security policies also have to be taken into account while comparing the security systems.
Finally, in Chapter 6, a comparison of the security schemes are made. In conclusion the bit matrix approach is seen to provide the following features.
(a) The time required to check if an access request should be honoured is very small.
(b) The time required to find a11 users accessing an object viz, accountability is quite small.
(c) The time required to find all objects accessible by a user is also quite small.
(dl The scheme supports both decentralized and centralized authorization control.
(e) Mechanism for enforcing delegation of access rights and revocation of access rights could be built in easily.
( f ) The scheme supports content-dependent, context-dependent controls and also provides a means for enforcing history-dependent control.
Finally, some recommendations for further study in the field of Computer Database Security are presented