shareengineer

GODS IN VEDA

2014-03-08T01:42:00.000-08:00

Vedas really say this...

Now this is what really amazed me. Vedas, which belongs to the history of the Hindus, really speaks directly about Jesus being the only Lord and Savior of this world. It also gives all the signs and wonders accompanying the Messiah of this World, Jesus. Just read on.

BACK TO VEDAS

All true seekers of God will desire for truth and welcome truth that leads them to the Living, Loving, Almighty and the All-powerful Creator. It is not just about religions, or sects, or faiths, nor is it a mere collection of some facts, but it is the driving force behind all sincere seekers to the ultimate hope of experiencing God.

It is in this pursuit that men for ages have been looking towards nature, ancestors, heroes and even to unknown spirits for help. In the course of time, they had started worshiping them as well. It is this longing that resulted in the birth of Vedas.

VEDAS:

Veda means, sacred scriptural knowledge. This knowledge was obtained through dedication, devotion and meditation, by several hundred Sages for years.

These scriptures are divided into two parts. One in Shruti (which is revealed) and the other one is Smruti (which is believed). Shruti contains Vedas (which gives light or knowledge); Smruti contains Ithihasas (parables like Maha Bharat, Ramayana and Bhagavat Gita) and Puranas. These Ithihasas and Puranas were written at latter date to explain the morals of these Vedas.

There are few classes of Vedas. The first one is called the Samhitaas or Mantras, the second one is Aagamas (Commandments), the third one is Bhramanas (this contains the meanings for Samhitaas) and the fourth one is the Aranyakas and Upanishads (which contains philosophies and meditations).

Again the Samhitaas are of four different types. The first one is the Rig Veda Samhitaa (which is a collection of Hymns). The second one is the Yazur Veda Samhitaa (a collection of sacrificial formulas). The third one is Sama Veda Samhitaa (again a collection of songs). The fourth one is the Atharva Veda Samhitaa (a collection of spells and charms).

GODS IN VEDA:

Vedas begin with the worship of gods of nature, namely;

The terrestrial gods- Prithvi (earth), Agni (fire), Bruhaspati and Soma (plants).

The atmospheric gods- Indra, Rudra, Maruts, Vayu and Parjanya (storm, thunder and rain).

The celestial gods- Dyaus (heaven), Varuna, Ushas & Asvins (twilight morning stars) and Surya, Mitra, Savitri, Ka, Vishnu (all associated with the sun).

As we have already seen, these gods were the result of man’s search for the truth, which finally culminated in Prajapati the Creator. The 10^th mandala of Rig Veda chapter 121 verse 10 says, Prajapati Lord of life, Lord of Creatures and Lord of Creations. This understanding of the Creator, made man to cry to Him, as it is written in Bhruhat Aranyaka Upanishad (1.3.28) saying, Asatoma sat gamaya, Tamasoma Jyotir gamaya, Mruthyoma amrutham gamaya, which means, from untruth lead me to truth, from darkness lead me to light, from death lead me to eternal life.

After having reached this stage of knowing the truth, the next step is obviously to follow the truth, which will ultimately help mankind to attain mukti. It is at this stage, that man comes across the major hurdle, which is very well described in Prartha Snana Mantra,

Papokam, papa kanmokam, papathma papa samphava; thrahimam Pundarikaksha sarva papa hari hare…

Which means, I am born in sin, doer of sin, and a sinful self; I am the worst of all sinners, Lord save me from all my sins. Why sin is a hurdle? Because, it is an offense against God (Rig Veda 7.86.3). Sin has many names in Sanskrit Scriptures namely pap (sin), aagg (fire), dushkrit (evil deeds), thamas(darkness), prakrit (inborn nature), asathya (untruth) etc.

Dr. S. Radhakrishnan says, we have sin with us from the beginning of history. The Bruhad Aranyaka Upanishad says, that the Jeeva (soul) acquires evil, right at birth (4.3.8). Rog Sog Dhuk Paritab Bhandan Vyasnanicha, Aatma aparatha Vrukshanam phalarh edhani dehinam, is a common saying which means, “what are the fruits of this sinful tree which is our body? Sickness, sorrow, pain, bondage and many other kinds of sins”. No man is free from this bondage of sin.

HOW TO GET RID OF THIS BONDAGE:

Man out of his own wisdom and knowledge, invented many ways such asKarma marga (way of works), Gnana marga (way of knowledge), Yoga marga (way of concentrating mind) and Bhakti marga (way of devotion), to get rid of this bondage of sin.

The word Karma means several things. (a) It may mean the deed or deeds of the individual human being. These deeds are (i) Satvik- virtuous, (ii) Rajasik- pride, (iii) Tamasik- evil. These three are known Triguna or triple nature. (b) It may mean the Cycle of karma, karma samsara or karma chakra. (c) It may also mean karma yoga or nishkarma, or a deed or deeds done without any desire for reward.

An individual’s karma can be classified as follows:

Sanchit karma- the accumulated deeds of all previous births, which gets attached to the soul automatically at the time of each birth, in the rebirth cycle.

Kriymana karma- good or bad deeds that the soul may further accumulate.

Prarabdha karma- deeds which decides the destiny of the soul.

The main purpose of this rebirth cycle is, that the soul in each birth may reap the good or bad of all its karma of the past and present.

As per this doctrine, no one can ever know about his or her accumulated deeds, thereby not having any opportunity to correct his or her past, resulting in a hopeless uncertainty. In other words, karma is being stamped on the forehead of every human being, and the destiny of the soul is ceaselessly determined without the control of the individual. This has made Shri Shankaracharya to say in Bajagovindam,

Punarapi janana punarapi marana; Punarapi janani jadarey sayana;

Ih sansarey wah dustarey; Krupya parey pahi muararey,

which means, repeated birth, repeated death, and repeated lying in mother’s womb, is a difficult process to go through. Oh destroyer of death, save me by your grace.

MUKTI (Deliverance from sin) IS NOT BY KARMA OR DHARMA:

According to Bhagavat Gita, God does not accept karma either good or bad, as far as redemption of the soul is concerned (B.G 2.50). Viveka Chudamani verse 147 says that, “neither weapons, nor wind, nor fire, nor millions of deeds can remove this bondage. Only the wonderful sword of knowledge that comes out of discrimination sharpened by the grace of God can destroy it”. Again verse 6 says;

Vadhanthu shastrani yadhanthu devane, Kurvanthu karmanibajanthu devata,

Aatmaikayodena vinabpi mukitha, na chityathi bhramma shathanthrashpi.

Let them quote scriptures and sacrifice to gods; let them observe rituals and worship devatas (gods); but there is no liberation at all; no, not even in a hundred lifespans of Brahma put together, until the identity of one’s self with the Divine Self is realized.

Naham vedair na danena na ejyaya

sakya evamvidho drstavan asi mam yatha (Gita 11:53),

which means, neither by Vedic study, nor by austerities, nor by charities, nor by sacrifices can one behold Me. Nor by any works that you have done.

Regarding the rebirth cycle the Poet Shiva Vakkiar says; Once milked, the same milk cannot enter into the breast. Once the butter is taken out of the milk, the same butter cannot mix with the same milk. Neither the flower that falls, can become a flower again. Then how can a man or woman be born in this world several times?

Regarding Gnana marga, the Vedas and Upanishads say, that we have to know the Purusha (for He is the knowledge) who has sacrificed His life for mankind.Gurureva paraa vidya (God himself is the knowledge) is a good verse to know.

Regarding the Yoga marga or concentration of the mind, there is only one answer in the Vedas and Upanishads as to whom we should concentrate on. It is Purusha the Almighty again. Mind concentration contains three important steps.

Shravana (Hearing about God from the Guru),

Manana (Keep on thinking about what we have heard),

Nididhyaasana (profound and repeated meditation on the word of God and dwelling in Him).

Yoga simply means, “to unite with”. Whom to unite with should be obvious. It is the Supreme Lord or Purusha. Shankara the ancient sage admitted that union with God is attained by the grace of God (Viveka Chudamani 3). Also verse 56 says,

Na yogena na sankhyena karmanano na vidhya

Bhrahmathmaikkathva bodhena moksha; sidhyathey nanyatha,

which means, neither by yoga, nor by knowing self, nor by karma, nor by learning, but by the realization of one’s own identity with God, is liberation possible.

Bhakti marga (way of devotion) according to scholars means spiritual love. The only God whom we can love is Purusha. If we can concentrate on this Purusha, then we will find Him and love Him as well. The Rig Veda says, “whom shall we worship other than Prajapati (Purusha)”. Svetasvataara Upanishad (3.8) says, “By knowing Purusha, death is transcended. There is no other way”.

ATONEMENT FOR SINS:

Thertiriya Aranyaka verse 3 says, “Sarvapapa pariharo raktha prokshna mavasyam” which means, that the redemption is through shedding of blood only. For this purpose God allowed mankind to sacrifice animals, in order to make them realize that there is a penalty for everyone’s sins. Though the animal’s blood is not a substitute, it was expected that man would repent and turn away from his sinful ways, by seeing the blood of the animal which is being shed on his behalf. But mankind started practicing it just as a ritual, and thus came into condemnation.

If mankind were to be saved from this predicament, as Thertiriya Aranyaka 3^rd verse says again, “…thad raktham Paranatmena punyadena baliyagam” which means, that blood has to be through the sacrifice of God himself. The Purusha Sukta says, there is no other way other than the sacrifice of Purusha Prajapati. Purushao vava yagna (Chandokya Upanishad 3.16.1), God, the Purusha is the sacrifice. Sama Veda Dandiya Mahabhramanam says,“Prajapathi devapyam aathmanam yagnam kruthva prayachita” which means, God will offer himself as a sacrifice for the redemption of mankind. Sathpatha Bhramanam says, “Prajapathi yagnayaga”.

VEDIC REQUIREMENTS FOR THE SACRIFICIAL PURUSHA:

The Rig Veda specifies ten important requirements for the sacrificial Purusha.

SHOULD BE WITHOUT A BLEMISH (NISHKALANGA PURUSHA):

Kaatyaayana Srautasootram describes in chapter six, that water and fire were to be used for the purification of the animals, since blameless (defectless) animals are not available in this world.

THE PURUSHA HAS TO BE SEPARATED FROM OTHERS:

While sacrificing the horse, the sacrificial horse is always separated from other horses. A bush of thorns is usually placed on the head of the horse to inform the people that this horse is separated for the sacrifice. Also the head of the horse is considered to represent the Purusha (Sathapatha Brahmana 13^thkanda, 6.2.2).

THE PURUSHA HAS TO BE REJECTED BY HIS OWN PEOPLE:

In Itareya Brahmana it is written that the sacrificial animal should be rejected by its father, mother, brother, sister and friends (2.16).

THE YAGNA PURUSHA HAS TO SUFFER SILENTLY:

Rig Veda 5.46.1 says, “Like a horse I have yoked myself, well knowing to the pole. I seek neither release nor turning back”.

THE PURUSHA HAS TO BE TIED TO A POST:

In Satapata Brahmana it is written, never do they immolate an animal without tying it to a pole. “Na varute yapaat pasum alabhate kadachana (III-7.3.1)”. It is important to tie the animal to a sacrificial pillar before it is sacrificed. This pillar is called “Yupastampa (sacrificial pillar)”, which has now become a flag mast.

THE BLOOD OF THE SACRIFICIAL MAN SHOULD BE SHED:

Bruhat Aranyaka Upanishad (3.9.28.2) says, “Tvacha evasya rudhiram, prasyandi tvacha utpatah, Tasmaattadarunnaat praiti, raso vrukshadi vahataat”. As the sap comes of the cut tree, blood comes out of the Purusha who is cut.

THE SACRIFICED ANIMAL’S BONES SHOULD NOT BE BROKEN:

In Itareya Brahmana 2.6 it is stated that the sacrifice separates the twenty-six ribs of the animal without breaking them.

THE SACRIFICED PURUSHA SHOULD RETURN TO LIFE:

The Bruhat Aranyaka Upanishad says, “Yad Vruksho vrukshano rohati, mulannavatharah punah, martyah svinmrutyuna vruknah, kasmaanmulaat prarohati, Retasa iti maavocata, jivatastat praja yate, dhanaruh a iva val crau vruksho, anjasaa pretya sammbhava”, which means, if the tree is cut, it will grow again from its root. But after the man (martyah) was cut off by death, from which root does he come forth? Do not say that he is from the ratas (seed or semen) because ratas comes from the one who lives. Remember this man is dead. But this man (Purusha) comes alive on his own.

THE FLESH OF THE PURUSHA SHOULD BE EATEN BY HIS SAINTS:

In Satapata Brahmana (5.1.1.1,2) we find that Prajapati gave Himself up to them, thus the sacrifice became theirs, and indeed the sacrifice is the food of the gods (saints).

THE SACRIFICE IS FOR ALL:

Verse 8 in Purusha Sukta explains, Tasmaad yagnatsarvahutah, pasuntamscakre voayaryaa, naananyaan gramyaasca ye. By that sacrifice, all these originated: sprinkled ghee and all kinds of animals of the sky, forest and country. The significance of sprinkled ghee represents the original sacrifice.

Verse 9 of Purusha Sukta says: Tasmaad yagnat sarvahuta, nucha samaari jagnire, Chandaamsi jagnine, tasmaad yajustas naada jaayatah. From that sacrifice, Purusha offered everything that he had, including the Rig, Sama, Yazur Vedas and the Chandas (sacred writings).

HOW METICULOUSLY THESE VEDIC REQUIREMENTS HAVE BEEN FULFILLED IN JESUS CHRIST OF NAZARETH:

JESUS CHRIST WAS WITHOUT ANY BLEMISH:

In the Bible it is written, “Do not bring anything with a defect, because it will not be accepted on your behalf” (Leviticus 22:20). “Whether male or female, present before the Lord an animal without defect” (Leviticus 3:1). “In Him (Jesus Christ) there was no sin” (1 John 3:5).

JESUS CHRIST WAS SEPARATED FROM OTHERS:

The Bible says, “the soldiers platted a crown of thorns, and put it on his head, and they put on him a purple robe” John 19:2, thus separating Him from others.

JESUS CHRIST WAS REJECTED BY HIS OWN PEOPLE:

The Prophet Isaiah wrote, “He (Jesus Christ) was despised and rejected and they shouted to crucify him”. Jesus said on the cross, “Eloi, Eloi, lama sabachthani”, which means, “My God, My God, why have you forsaken me?” (Matthew 27:46).

JESUS CHRIST SUFFERED SILENTLY:

“He was oppressed and afflicted, yet He did not open his mouth. He was led like a lamb to the slaughter and as a sheep before the shearers is silent” (Isaiah 53:7).

JESUS CHRIST WAS TIED:

Psalms 118:27 says, “bind the sacrifice with cords, even unto the horns of the altar”.

JESUS CHRIST’S BLOOD WAS SHED:

This was fulfilled in Jesus Christ when he was nailed to the cross. “He did not enter by means of the blood of goats and calves; but entered the most holy place once for all by His own blood, having obtained eternal redemption. Without shedding of blood there is no redemption” (Hebrews 9:12,22).

JESUS CHRIST’S BONES WERE NOT BROKEN:

In the Bible, Exodus 12:46 says that the bones of the animal should not be broken. Nine hours after crucifixion, “when they (soldiers) came to Jesus, and saw that he was dead already, they broke not his legs” (John 19:33).

JESUS CHRIST ROSE AGAIN FROM THE DEAD:

“Him (Jesus Christ) God raised up the third day, and showed him openly” (Acts 10:40). “But now is Christ risen from the dead, and become the firstfruits of them that slept” (1 Corinthians 15:20).

JESUS CHRIST GAVE HIS BODY TO BE EATEN:

At the last supper Jesus took the bread, gave thanks and gave it to his disciples saying, “Take and eat; this is my body. Then He took the cup, gave thanks, and offered it to them, saying, Drink from it, all of you. This is my blood of the new covenant, which is shed for many, for the forgiveness of sins” (Matthew 26:26,27).

JESUS CHRIST WAS GIVEN TO ALL:

“He who did not spare His own son, but gave him up for us all, how will he not also, along with him graciously give us all things?” (Romans 8:32).

GOD’S PLAN FOR MOKSHA (ETERNAL LIFE):

For all have sinned, and come short of the glory of God. Romans 3:23.

All we like sheep have gone astray; we have turned everyone to his own way; and the LORD has laid on him the iniquity of us all. Isaiah 53:6.

For the wages of sin is death; but the gift of God is eternal life through Jesus Christ our Lord. Romans 6:23.

And according to the law almost all things are purged with the blood, and without shedding of blood there is no remission. Hebrews 9:22.

But God commended his love toward us, in that, while we were yet sinners, Christ died for us. Romans 5:8.

For He has made him to be sin for us, who knew no sin; that we might be made the righteousness of God in him. 2 Corinthians 5:21.

The blood of Jesus Christ, His Son cleanses us from all sin. 1 John 1:7.

For God so loved the world that He gave His only begotten son, that whosoever believes in him should not perish, but have everlasting life. John 3:16.

Herein is love, not that we loved God, but that he loved us, and sent His Son to be the propitiation for our sins. 1 John 4:10.

That if you shall confess with your mouth the Lord Jesus, and shall believe in your heart that God has raised him from the dead, you will be saved. Romans 10:9.

Or do you underestimate His wealth of kindness and tolerance and enduring patience, unmindful that God’s kindness is meant to lead you toward repentance?. But in line with your obstinacy and impenitence of heart you are treasuring up for yourself anger for the day of anger and the revealing of the righteous judgment of God, who will reward each person according to his deeds. Romans 2:4-6.

For there is no partiality with God. Romans 2:11.

Neither is there salvation in any other: for there is none other name under heaven given among men, whereby we must be saved. Acts 4:12.

So today if you hear His voice, harden not your heart, but come boldly unto the throne of grace, that you may obtain mercy, pardon and ETERNAL LIFE (MOKSHA).

Come unto Me, all ye that labor and are heavy laden, and I will give you rest. Matthew 11:28.

Behold, I stand at the door, and knock; if any man hear my voice, and open the door, I will come in to him, and will sup with him, and he with Me. Revelation 3:20.

I am the way, the truth and life; no one comes to the Father except through Me. John 14:6.

Verily, verily, I say unto you, he that hears My word, and believes in Him that sent Me, has everlasting life, and shall not come into condemnation; but is passed from death unto life. John 5:24.

For what shall it profit a man, if he shall gain the whole world, and lose his own soul? Mark 8:36.

SAHASRANAMAVALI ACKNOWLEDGES JESUS CHRIST:

Ohm Shri Brahmaputraya namaha: Oh Lord, The Son of God, we praise you.

Ohm Shri Umathyaya namaha: Oh Lord who is born of the Spirit, we praise you.

Ohm Shri kanni sudhaya namaha: Oh Lord who is born of a virgin, we praise you.

Ohm Shri tharithra narayanaya namaha: Oh Lord who became poor for our sake, we praise you.

Ohm Shri vidhiristaya namaha: Oh Lord who is circumcised, we praise you.

Ohm Shri panchagayaya namaha: Oh Lord who bore five wounds on your body, we praise you.

Ohm Shri vruksha shul aruthaya namaha: Oh Lord who offered yourself as a sacrifice on a trishool like tree (three headed spear), we praise you.

Ohm Shri mruthyam jaya namaha: Oh Lord who got victory over death, we praise you.

Ohm Shri shibilistaya namaha: Oh Lord who willingly offered your flesh to be eaten by your saints, we praise you.

Ohm Shri thatchina moorthyaya namaha: Oh Lord who is seated by the side of the Father, we praise you.

Ohm Shri maha devayaya namaha: Oh Lord who is Lord of lords, we praise you.

JESUS CHRIST IN BHAVISHYA MAHAPURANA:

Bhavishya Mahapurana, book three, chapter two, verse 34 says, “Ko bhavaanithi tham praaha Sobhovaachamudaanwitha: Eshaputhram cha maam vidhi Kumaaree garbha sambahavam Aham Eesa Maseeha nama:”which means, (king Saka asks) “May I know who you are? That man replied happily, I am the Son of God, born to a virgin. My name is Eesa Maseeha.”.

CULTURAL AND THEOLOGICAL IDENTITY:

The festival of Shivarathri is celebrated by keeping a vigil throughout that night to thank god who had saved a hunter, who lost his way in the jungle.

The Bible says that the Lord kept a vigil on the day of Passover and delivered the people of Israel from Egypt. In remembrance of this day and to honor the Lord, the Israelites in turn keep a vigil on this night every year.

On this day, God instructed Moses to mark the main doors of their houses and the top and two side posts with the blood of the lamb, which was to be sacrificed by each family, as a mark of identification for the purpose of protection. These same markings with the red powder can be seen in every Indian house, even today.

While on a journey, Jacob slept for the night by keeping a stone as a pillow and dreamt, seeing angels of God ascending and descending on a ladder set between earth and heaven, and the Lord stood above it. Next morning he took the stone, and set it up as a pillar, and poured oil over it, and he named that place as Bethel (house of God). In India also one can see the stone with oil, which has become “Shivalinga”.

In the Bible, God told Moses to bring a red heifer without spot and kill it as a sacrifice for the Lord. Her skin, her flesh, blood and dung shall be burnt. A clean man shall gather up the ashes of the heifer and keep it in the holy place. This ash will be mixed with water and will be sprinkled on the body of the people, for the purpose of purification from their sins (Numbers 19:1-9).

During the Vedic period, three different kinds of sacrifices were in practice. 1.Nara (human) medhya (body) yagna (sacrifice), 2. Ko (cow) medhya yagna, 3. Aswa medhya yagna. For Ko medhya yagna, the cow should be a red one. Even today, if a Brahmin wants to do some ceremonial duty in his house, he will look for a red cow and do pooja before it. The sacrificial cow has now become a sacred cow, because cow is no longer sacrificed by law. Therefore, people burn only the cow’s dung and they collect these ashes and mix it with water and apply it on their body or generally on their forehead as “Vibhooti”.

Since the sacrificed cow was to be positioned upside down on the altar before burning, a long three headed fork like tool was used. In addition, to collect and store these ashes, several types of vessels were used. In the Bible the Lord told, “you shall make its pans to receive its ashes, and its shovels and its basins and its forks and its fire pans; you shall make all its utensils of bronze” (Exodus 27:3).

Similarly in the Indian temples also, all these vessels are made out of bronze. Ever since the sacrifices have been stopped, the meat fork with three-headed spear is kept near the altar in front of the temple. This has now become “Trishool”.

In the Bible, the priest, while he is inside the holy of the holiest part of the temple, should make a sound with the bells, as well as while coming out of it. He should have his undergarments from the waist to the knee. The sacrificial animal should have a small string, bearing the name of the family. The priest should mention the name of the family and then sacrifice. He should wear an engraved plate on his turban saying, “Holy to the Lord” (Exodus 28:34-37,42).

In the Indian temples also, when the priest goes inside the holy of the holiest place for prayer, he makes the noise of the bell and comes out with the noise of the bell. He wears a piece of cloth from his hip to the knee over his clothing. When the people bring their offerings to God, he always asks them on whose name should it be offered?

As the Bible says, that “God is a Spirit, and they that worship him must worship him in spirit and in truth (John 4:24)”, the Yazur Veda also says,“Nathasya prathima asityasya nammahastha (32:3)”, God has no image and His name is Holy.

The Bruhat Aranyaka Upanishad says, “Vagya vai Brahmma”, the word is Brahmma (creator). Brahmmavindu Upanishad says, “Shabdo vai Brahmma”, the voice is Brahmma and “Shabdaksharam Param Brahmma”, the voice and word became absolute God.

The Bible says, “In the beginning was the Word, and the Word was with God, and the Word was God … and the Word was made flesh (Jesus)” (John 1:1,14).

At His Service,

Nimmathi Nilayam,

P.O. Box- 8659,

Chennai- 600041.

the_word_of_truth_ministries@yahoo.com

MODELING AND DESIGN IN OODBMS

2013-01-06T22:04:00.001-08:00

Basically, an OODBMS is an object database that provides DBMS capabilities to objects thathave been created using an object-oriented programming language (OOPL). The basic principle is to add persistence to objects and to make objects persistent.

Consequently application programmers who use OODBMSs typically write programs in a native OOPL such as Java, C++ or Smalltalk, and the language has some kind of Persistent class, Database class, Database Interface, or Database API that provides DBMS functionality as, effectively, an extension of the OOPL.

Object-oriented DBMSs, however, go much beyond simply adding persistence to any one object-oriented programming language. This is because, historically, many object-oriented DBMSs were built to serve the market for computer-aided design/computer-aided manufacturing (CAD/CAM) applications in which features like fast navigational access,

versions, and long transactions are extremely important.

Object-oriented DBMSs, therefore, support advanced object-oriented database applications with features like support for persistent objects from more than one programming language, distribution of data, advanced transaction models, versions, schema evolution, and dynamic generation of new types.

Object data modeling

An object consists of three parts: structure (attribute, and relationship to other objects like aggregation, and association), behavior (a set of operations) and characteristic of types (generalization/serialization). An object is similar to an entity in ER model; therefore we begin with an example to demonstrate the structure and relationship.

Attributes are like the fields in a relational model. However in the Book example we have,for attributes publishedBy and writtenBy, complex types Publisher and Author,which are also objects. Attributes with complex objects, in RDNS, are usually other tableslinked by keys to the employee table.

Relationships: publish and writtenBy are associations with I:N and 1:1 relationship; composed_of is an aggregation (a Book is composed of chapters). The 1:N relationship is usually realized as attributes through complex types and at the behavioral level. For example,

Generalization/Serialization is the is_a relationship, which is supported in OODB through class hierarchy. An ArtBook is a Book, therefore the ArtBook class is a subclass of Book class. A subclass inherits all the attribute and method of its superclass.

Message: means by which objects communicate, and it is a request from one object to another to execute one of its methods. For example:

Publisher_object.insert (”Rose”, 123,…) i.e. request to execute the insert method on a Publisher object )

Method: defines the behavior of an object. Methods can be used

. to change state by modifying its attribute values . to query the value of selected attributes The method that responds to the message example is the method insert defied in the Publisher class.

The main differences between relational database design and object oriented database design include:

• Many-to-many relationships must be removed before entities can

be translated into relations. Many-to-many relationships can be implemented directly in an object-oriented database.

• Operations are not represented in the relational data model.

Operations are one of the main components in an object-oriented

database.

• In the relational data model relationships are implemented by

primary and foreign keys. In the object model objects communicate through their interfaces. The interface describes the data (attributes) and operations (methods) that are visible to other objects.

OBJECT ORIENTED DATA BASE OODB& RELATIONAL DB

2013-01-06T21:55:00.003-08:00

TRANSACTION PROCESSING

2013-01-06T21:49:00.001-08:00

Transaction

A transaction is a collection of actions that make consistent transformations of system states while preserving system consistency.

à concurrency transparency

à failure transparency

INTRODUCTION TO OBJECT ORIENTED DATA BASES

2013-01-06T21:48:00.001-08:00

Object Databases

Ø Became commercially popular in mid 1990’s

Ø You can store the data in the same format as you use it. No paradigm shift.

Ø Did not reach full potential till the classes they store were decoupled from the database schema.

Ø Open source implementation available – low cost solution now exists.

What is Object Oriented Database? (OODB)

Ø A database system that incorporates all the important object-oriented concepts

Ø Some additional features

o Unique Object identifiers

o Persistent object handling

Ø Is the coupling of Object Oriented (OOP) Programming principles with Database Management System (DBMS) principles

o Provides access to persisted objects using the same OO-programming language

Advantages of OODBS

Ø Designer can specify the structure of objects and their behavior (methods)

Ø Better interaction with object-oriented languages such as Java and C++

Ø Definition of complex and user-defined types

Ø Encapsulation of operations and user-defined methods

Object Database Vendors

Ø Matisse Software Inc.,

Ø Objectivity Inc.,

Ø Poet's FastObjects,

Ø Computer Associates,

Ø eXcelon Corporation

Ø Db4o

1.4 QUERY PROCESSING

2013-01-06T21:45:00.000-08:00

Ø using client-server architecture

Ø user creates query

Ø client parses and sends to server(s) (SQL?)

Ø servers return appropriate Tables

Ø client combines into one Table

Ø Issue of data transfer cost over a network

o optimise the query to transfer the least amount

Query Processing Components

Ø Query language that is used

o SQL: “intergalactic dataspeak”

Ø Query execution methodology

o The steps that one goes through in executing high-level (declarative) user queries.

Ø Query optimization

o How do we determine the “best” execution plan?

Query Optimization Objectives

Ø Minimize a cost function

§ I/O cost + CPU cost + communication cost

Ø These might have different weights in different distributed environments

Ø Wide area networks

o communication cost will dominate

§ low bandwidth

§ low speed

§ high protocol overhead

o most algorithms ignore all other cost components

Ø Local area networks

o communication cost not that dominant

o total cost function should be considered

Ø Can also maximize throughput

Query Optimization Issues – Types of Optimizers

Ø Exhaustive search

o cost-based

o optimal

o combinatorial complexity in the number of relations

Ø Heuristics

o not optimal

o regroup common sub-expressions

o perform selection, projection first

o replace a join by a series of semijoins

o reorder operations to reduce intermediate relation size

o optimize individual operations

Optimization Granularity

Ø Single query at a time

o cannot use common intermediate results

Ø Multiple queries at a time

o efficient if many similar queries

o decision space is much larger

Optimization Timing

Ø Static

o compilation Þ optimize prior to the execution

o difficult to estimate the size of the intermediate results Þ error propagation

o can amortize over many executions

o R*

Ø Dynamic

o run time optimization

o exact information on the intermediate relation sizes

o have to reoptimize for multiple executions

o Distributed INGRES

Ø Hybrid

o compile using a static algorithm

o if the error in estimate sizes > threshold, reoptimize at run time

o MERMAID

Statistics

Ø Relation

o cardinality

o size of a tuple

o fraction of tuples participating in a join with another relation

Ø Attribute

o cardinality of domain

o actual number of distinct values

Ø Common assumptions

o independence between different attribute values

o uniform distribution of attribute values within their domain

Decision Sites

Ø Centralized

o single site determines the “best” schedule

o simple

o need knowledge about the entire distributed database

Ø Distributed

o cooperation among sites to determine the schedule

o need only local information

o cost of cooperation

Ø Hybrid

o one site determines the global schedule

Ø each site optimizes the local subqueries

Network Topology

Ø Wide area networks (WAN) – point-to-point

o characteristics

§ low bandwidth

§ low speed

§ high protocol overhead

o communication cost will dominate; ignore all other cost factors

o global schedule to minimize communication cost

o local schedules according to centralized query optimization

Ø Local area networks (LAN)

o communication cost not that dominant

o total cost function should be considered

o broadcasting can be exploited (joins)

o special algorithms exist for star networks

Step 1 – Query Decomposition

§ Input : Calculus query on global relations

Ø Normalization

o manipulate query quantifiers and qualification

Ø Analysis

o detect and reject “incorrect” queries

o possible for only a subset of relational calculus

Ø Simplification

o eliminate redundant predicates

Ø Restructuring

o calculus query Þ algebraic query

o more than one translation is possible

o use transformation rules

Step 2 – Data Localization

Ø Input: Algebraic query on distributed relations

Ø Determine which fragments are involved

Ø Localization program

o substitute for each global query its materialization program

o optimize

Step 3 – Global Query Optimization

Ø Input: Fragment query

Ø Find the best (not necessarily optimal) global schedule

o Minimize a cost function

o Distributed join processing

§ Bushy vs. linear trees

§ Which relation to ship where?

§ Ship-whole vs ship-as-needed

o Decide on the use of semijoins

§ Semijoin saves on communication at the expense of more local processing.

o Join methods

§ nested loop vs ordered joins (merge join or hash join)

Centralized Query Optimization

Ø INGRES

o dynamic

o interpretive

Ø System R

o static

o exhaustive search

12 Rules of DDBMS (Date, 1987)

1. Local autonomy

2. No reliance on a central site

3. Continuous operation

4. Location independence

5. Fragmentation independence

6. Replication independence

7. Distributed Query processing

8. Distributed transaction processing

9. Hardware independence

10. Operating System independence

11. Network independence

12. Database independence

1.1 DISTRIBUTED DATABASES VS CONVENTIONAL DATABASES

2013-01-06T21:42:00.003-08:00

Ø mimics organisational structure with data

Ø local access and autonomy without exclusion

Ø cheaper to create and easier to expand

Ø improved availability/reliability/performance by removing reliance on a central site

Ø Reduced communication overhead

§ Most data access is local, less expensive and performs better

Ø Improved processing power

§ Many machines handling the database rather than a single server

Ø more complex to implement

Ø more costly to maintain

Ø security and integrity control

Ø standards and experience are lacking

Ø Design issues are more complex

1.2 DISTRIBUTED DATABASES ARCHITECTURE

Ø Defines the structure of the system

o components identified

o functions of each component defined

o interrelationships and interactions between components defined

What is a distributed database?

l“A logically interrelated collection of shared data (and a description of this data), physically distributed over a computer network”

Implicit Assumptions

Ø Data stored at a number of sites ï each site logically consists of a single processor.

Ø Processors at different sites are interconnected by a computer network ï no multiprocessors

o parallel database systems

Ø Distributed database is a database, not a collection of files ï data logically related as exhibited in the users’ access patterns

o relational data model

Ø D-DBMS is a full-fledged DBMS

o not remote file system, not a TP system

Advantages of distributed databases

Ø Capacity and incremental growth

Ø Increase reliability and availability

Ø Modularity

Ø Reduced communication overhead

Ø Protection of valuable data

Ø Efficiency and Flexibility

Disadvantages of distributed databases

Ø DDB design more complex, fragmentation & replication; extra work must be done by the DBAs to ensure that the distributed nature of the system is transparent.

Ø Economics,

Ø Concurrency control,

Ø Inexperience,

Ø Security,

Ø Difficult to maintain integrity

Applications

Ø Manufacturing - especially multi-plant manufacturing

Ø Military command and control

Ø Electronic fund transfers and electronic trading

Ø Corporate MIS

Ø Airline restrictions

Ø Hotel chains

Ø Any organization which has a decentralized organization structure

B.E/B.TECH ADVANCED COMPUTER ARCHITECTURE

2013-01-04T22:04:00.001-08:00

1	Fundamentals of computer design
2	Measuring and reporting performance
3	Quantitative principles of computer design
4	ISA
6	Pipelining
5	Deign issues ISA
7	Pipeline hazard
8	Implementation
9	Multicycle operation
10	Instruction Level Parallelism
11	Dynamic scheduling
12	Dynamic hardware prediction
13
14	Multiple Issue
15	Hardware based speculation
16	Limitations of ILP
17	case study
18	Compiler techniques for exposing ILP
20	Static branch prediction
21	Hardware support for exposing more parallelism
22	Hardware vs software speculation mechanism
23	Case study
24	Symmetric shared memory architecture
25	distributed shared memory and directory based coherence
26	Performance issues
27	Synchronisation issues
28	Models of memory consistency
29	Software and hardware multithreading
30	SMT architecture
31	CMP architecture
32	Case study
33	Cache performance
34	Reducing cache miss penalty
35	Reducing hit time
36	Main memeory and performance
37	Memory Technology
38	Types of storage devices
39	Buses and RAID
40	Reliability, availability and dependability
41	I/O performance

M.E/M.TECH ADVANCED COMPUTER ARCHITECTURE NOTES

2013-01-04T22:00:00.004-08:00

1	Fundamentals of computer design
2	Measuring and reporting performance
3	Quantitative principles of computer design
4	ISA
6	Pipelining
5	Deign issues ISA
7	Pipeline hazard
8	Implementation
9	Multicycle operation
10	Instruction Level Parallelism
11	Dynamic scheduling
12	Dynamic hardware prediction
13
14	Multiple Issue
15	Hardware based speculation
16	Limitations of ILP
17	case study
18	Compiler techniques for exposing ILP
20	Static branch prediction
21	Hardware support for exposing more parallelism
22	Hardware vs software speculation mechanism
23	Case study
24	Symmetric shared memory architecture
25	distributed shared memory and directory based coherence
26	Performance issues
27	Synchronisation issues
28	Models of memory consistency
29	Software and hardware multithreading
30	SMT architecture
31	CMP architecture
32	Case study
33	Cache performance
34	Reducing cache miss penalty
35	Reducing hit time
36	Main memeory and performance
37	Memory Technology
38	Types of storage devices
39	Buses and RAID
40	Reliability, availability and dependability
41	I/O performance

Synchronisation issues

2013-01-04T21:50:00.000-08:00

Synchronisation issues

Synchronization mechanisms are typically built with user-level software routines that rely on hardware supplied synchronization instructions.

For smaller multiprocessors or low-contention situations, the key hardware capability is an uninterruptible instruction or instruction sequence capable of atomically retrieving.

In larger-scale multiprocessors or high-contention situations, synchronization can become a performance bottleneck because contention introduces additional delays and because latency is potentially greater in such a multiprocessor.

Basic Hardware Primitives

The key ability we require to implement synchronization in a multiprocessor is asset of hardware primitives with the ability to atomically read and modify a memory location.

There are a number of alternative formulations of the basic hardware primitives, all of which provide the ability to atomically read and modify a location, together with some way to tell if the read and write were performed atomically

These hardware primitives are the basic building blocks that are used to build a wide variety of user-level synchronization operations, including things such as locks and barriers.

One typical operation for building synchronization operations is atomic exchange, which interchanges a value in a register for a value in memory.

To see how to use this to build a basic synchronization operation, assume that we want to build a simple lock where the value 0 is used to indicate that the lock is freehand 1 is used to indicate that the lock is unavailable.

A processor tries to set the lock by doing an exchange of 1, which is in a register, with the memory address corresponding to the lock.

For example, consider two processors that each try to do the exchange simultaneously: This race is broken since exactly one of the processors will perform the exchange first, returning 0, and the second processor will return 1 when it does the exchange.

The key to using the exchange (or swap) primitive to implement synchronization is that the operation is atomic: The exchange is indivisible, and two simultaneous exchanges will be ordered by the write serialization mechanisms.

It is impossible for two processors trying to set the synchronization variable in this manner to both think they have simultaneously set the variable.

There are a number of other atomic primitives that can be used to implement synchronization

One operation, present in many older multiprocessors, is test-and-set, which tests a value and sets it if the value passes the test.

For example, we could define an operation that tested for 0 and set the value to 1, which can be used in a fashion similar to how we used atomic exchange.

Another atomic synchronization primitive is fetch-and-increment: It returns the value of a memory location and atomically increments it.

This requirement complicates the implementation of coherence, since the hardware cannot allow any other operations between the read and the write, and yet must not deadlock.

An alternative is to have a pair of instructions where the second instruction returns a value from which it can be deduced whether the pair of instructions was executed as if the instructions were atomic.

The pair of instructions includes a special load called a load linked or load locked and a special store called a store conditional.

These instructions are used in sequence: If the contents of the memory location specified by the load linked are changed before the store conditional to the same address occurs, then the store conditional fails.

The store conditional is defined to return 1 if it was successful and a 0 otherwise.

An advantage of the load linked/store conditional mechanism is that it can be used to build other synchronization primitives. For example, here is an atomic fetch-and-increment:

LL R2,0(R1) ;load linked

DADDUI R3,R2,#1 ;increment

SC R3,0(R1) ;store conditional

BEQZ R3,try ;branch store fails

These instructions are typically implemented by keeping track of the address specified in the LL instruction in a register, often called the link register.

If an interrupt occurs, or if the cache block matching the address in the link register is invalidated (for example, by another SC), the link register is cleared.

In addition, the number of instructions between the load linked and the store conditional should be small to minimize the probability that either an unrelated event or a competing processor causes the store conditional to fail frequently

I/O performance measures and Designing I/O

2013-01-04T21:08:00.004-08:00

I/O performance has measures that have no counterparts in CPU design. One of

these is diversity: Which I/O devices can connect to the computer system? An-

other is capacity: How many I/O devices can connect to a computer system?

In addition to these unique measures, the traditional measures of performance,

namely response time and throughput, also apply to I/O. (I/O throughput is some-

times called I/O bandwidth, and response time is sometimes called latency.)

Another measure of I/O performance is the interference of I/O with CPU execution. Transferring data may interfere with the execution of another process. There is also overhead due to handling I/O interrupts. Our concern here is how much longer a process will take because of I/O for another process.

Throughput versus Response Time

An interaction, or transaction, with a computer is divided into three parts:

1. Entry time—The time for the user to enter the command. The graphics system

in Figure 7.26 required 0.25 seconds on average to enter a command versus

4.0 seconds for the keyboard system.

2. System response time—The time between when the user enters the command

and the complete response is displayed.

3. Think time—The time from the reception of the response until the user begins

to enter the next command.

The sum of these three parts is called the transaction time. Several studies report

that user productivity is inversely proportional to transaction time; transactions

per hour are a measure of the work completed per hour by the user.

Whether these results are explained as a better match to the human attention

Designing an I/O system.

The art of I/O system design is to find a design that meets goals for cost, depend-

ability, and variety of devices while avoiding bottlenecks in I/O performance and

dependability. Avoiding bottlenecks means that components must be balanced

between main memory and the I/O device, because performance and dependabil-

ity—and hence effective cost-performance or cost-dependability—can only be as

good as the weakest link in the I/O chain. The architect must also plan for expan-

sion so that customers can tailor the I/O to their applications. This expansibility,

both in numbers and types of I/O devices, has its costs in longer I/O buses and

networks, larger power supplies to support I/O devices, and larger cabinets.

In designing an I/O system, we analyze performance, cost, capacity, and

availability using varying I/O connection schemes and different numbers of I/O

devices of each type. Here is one series of steps to follow in designing an I/O sys-

tem. The answers for each step may be dictated by market requirements or sim-

ply by cost, performance, and availability goals.

1. List the different types of I/O devices to be connected to the machine, or list

the standard buses and networks that the machine will support.

2. List the physical requirements for each I/O device. Requirements include size,

power, connectors, bus slots, expansion cabinets, and so on.

3. List the cost of each I/O device, including the portion of cost of any controller

needed for this device.

4. List the reliability of each I/O device.

5. Record the processor resource demands of each I/O device. This list should

include

Clock cycles for instructions used to initiate an I/O, to support operation

of an I/O device (such as handling interrupts), and to complete I/O

Processor clock stalls due to waiting for I/O to finish using the memory,

bus, or cache

Processor clock cycles to recover from an I/O activity

6. List the memory and I/O bus resource demands of each I/O device. Even when

the processor is not using memory, the bandwidth of main memory and the I/O

connection is limited.

7. The final step is assessing the performance and availability of the different

ways to organize these I/O devices. When you can afford it, try to avoid single

points of failure. Performance can only be properly evaluated with simulation,

although it may be estimated using queuing theory. Reliability can be calcu-

lated assuming I/O devices fail independently and that the times to failure are

exponentially distributed. Availability can be computed from reliability by esti-

mating MTTF for the devices, taking into account the time from failure to

repair.

Reliability, availability and dependability

2013-01-04T21:07:00.001-08:00

One persistent shortcoming with the general topic of making computers systems that can survive component faults has been confusion over terms. Consequently, perfectly good words like “reliability” and “availability” have been abused over the years so that their precise meaning is unclear.

Defining Failure:

Laprie picked a new term––dependability–– to have a clean slate to work with:

Computer system dependability is the quality of delivered service such that re- liance can justifiably be placed on this service. The service delivered by a sys- tem is its observed actual behavior as perceived by other system(s) interacting with this system’s users. Each module also has an ideal speci?ed behavior, where a service speci?cation is an agreed description of the expected behavior.

A system failure occurs when the actual behavior deviates from the specified behavior. The failure occurred because an error, a defect in that module. The cause of an error is a fault.

When a fault occurs it creates a latent error, which becomes effective when it is activated; when the error actually affects the delivered service, a failure oc- curs. The time between the occurrence of an error and the resulting failure is the error latency. Thus, an error is the manifestation in the system of a fault, and a failure is the manifestation on the service of an error.

To clarify, the relation between faults, errors, and failures is:

A fault creates one or more latent errors.
The properties of errors are

1) a latent error becomes effective once activated;

2) an error may cycle between its latent and effective states;

3) an effective error often propagates from one component to another, thereby creating new errors. Thus, an effective error is either a formerly latent error in that componentor it has propagated from another error in that component or from elsewhere.

A component failure occurs when the error affects the delivered service.
These properties are recursive, and apply to any component in the system.

Users perceive a system alternating between two states of delivered service with respect to the service speci?cation:

1. Service accomplishment, where the service is delivered as specified,

2. Service interruption, where the delivered service is different from the speci-

fied service.

Transitions between these two states are caused by failures (from state 1 to

state 2) or restorations (2 to 1). Quantifying these transitions lead to the two

main measures of dependability:

1. Module reliability is a measure of the continuous service accomplishment (or,

equivalently, of the time to failure) from a reference initial instant. The overall

failure rate of the collection is the sum of the failure rates of the modules. Ser-

vice interruption is measured as Mean Time To Repair (MTTR).

2. Module availability is a measure of the service accomplishment with respect

to the alternation between the two states of accomplishment and interruption.

For non-redundant systems with repair, module availability is statistically

quantified as:

Module availability = MTTF

-------------------------------

(MTTF+MTTR)

Note that reliability and availability are now quantifiable metrics, rather than

synonyms for dependability. Mean Time Between Failures (MTBF) is simply

the sum of MTTF + MTTR. Although MTBF is widely used, MTTF is often

the more appropriate term.

Classifying faults and fault tolerance techniques may aid with understanding.

Gray and Siewiorek classify faults into four categories according to their cause:

1. Hardware faults: devices that fail.

2. Design faults: faults in software (usually) and hardware design (occasionally).

3. Operation faults: mistakes by operations and maintenance personnel.

4. Environmental faults: fire, flood, earthquake, power failure, and sabotage.

Faults are also classified by their duration into transient, intermittent, and perma-

nent [Nelson 1990]. Transient faults exist for a limited time and are not recurring.

Intermittent faults cause a system to oscillate between faulty and fault free opera-

tion. Permanent faults do not correct themselves with passing of time.

Reliability improvements into four methods:

1. Fault avoidance: how to prevent, by construction, fault occurrence;

2. Fault tolerance: how to provide, by redundancy, service complying with the

service specification in spite of faults having occurred or are occurring;

3. Error removal: how to minimize, by verification, the presence of latent errors;

4. Error forecasting: how to estimate, by evaluation, the presence, creation, and

consequences of errors.

Buses and RAID

2013-01-04T21:06:00.005-08:00

In a computer system, the various subsystems must have interfaces to one another; for instance, the memory and CPU need to communicate, and so do the CPU and I/O devices. This communication is commonly done using a bus. The bus serves as a shared communication link between the subsystems. The two major advantages of the bus organization are low cost and versatility...

The major disadvantage of a bus is that it creates a communication bottleneck,

Possibly limiting the maximum I/O throughput . To avoid the bus bottleneck, some I/O devices

are connected to computers via Storage Area Networks (SANs).

One reason bus design is so difficult is that the maximum bus speed is largely

limited by physical factors: the length of the bus and the number of devices (and, hence, bus loading). These physical limits prevent arbitrary bus speedup. The desire for high I/O rates (low latency) and high I/O throughput can also lead to conflicting design requirements.

Buses were traditionally classified as CPU-memory buses or I/O buses. I/O

buses may be lengthy, may have many types of devices connected to them, have a wide range in the data bandwidth of the devices connected to them, and normally follow a bus standard.

CPU-memory buses, on the other hand, are short, generally high speed, and matched to the memory system to maximize memory-CPU bandwidth. During the design phase, the designer of a CPU-memory bus knows all the types of devices that must connect together, while the I/O bus designer must accept devices varying in latency and bandwidth capabilities.

To lower costs, some computers have a single bus for both memory and I/O devices. In the quest for higher I/O performance, some buses are a hybrid of the two. For example, PCI is relatively short, and is used to connect to more traditional I/O buses via bridges

that speak both PCI on one end and the I/O bus protocol on the other. To indicate

its intermediate state, such buses are sometimes called mezzanine buses.

Bus Design Decisions

The design of a bus presents several options

If there are multiple masters, an arbitration scheme is required among the masters to decide which one gets the bus next. Arbitration is often a fixed priority for each device, as is the case with daisy-chained devices, or an approximately fair scheme that randomly chooses which master gets the bus. With multiple masters, a bus can offer higher bandwidth by using packets, as opposed to holding the bus for the full transaction. This technique is called split transactions

The final item clocking, concerns whether a bus is synchronous or asynchronous. If a bus is synchronous, it includes a clock in the control lines and a fixed protocol for sending address and data relative to the clock. An asynchronous bus, on the other hand, is not clocked. Instead, self-timed, handshaking protocols are used between bus sender and receiver.

Bus Standards

The number and variety of I/O devices is flexible on many computers, permitting customers to tailor computers to their needs. The I/O bus is the interface to which devices are connected. Standards that let the computer designer and I/O-device designer work independently play a large role in buses.

As long as both designers meet the requirements, any I/O device can connect to any computer. The I/O bus standard is the document that defines how to connect devices to computers.

Machines sometimes grow to be so popular that their I/O buses become the facto standards

RAID

An innovation that improves both dependability and performance of storage systems is disk arrays. One argument for arrays is that potential throughput can be increased by having many disk drives and, hence, many disk arms, rather than one large drive with one disk arm.

Simply spreading data over multiple disks, called striping, au-

tomatically forces accesses to several disks. (Although arrays improve throughput, latency is not necessarily improved.) The drawback to arrays is that with more devices, dependability decreases: N devices generally have 1/N the reliability of a single device.

No Redundancy (RAID 0)

This notation is refers to a disk array in which data is striped but there is no redundancy to tolerate disk failure. Striping across a set of disks makes the collection appear to software as a single large disk, which simpli?es storagemanagement. It also improves performance for large accesses, since many diskscan operate at once. Video editing systems, for example, often stripe their data.

Mirroring (RAID 1)

This traditional scheme for tolerating disk failure, called mirroring or shadowing, uses twice as many disks as does RAID 0. Whenever data is written to one disk, that data is also written to a redundant disk, so that there are always two copies of the information. If a disk fails, the system just goes to the “mirror” to get the de-sired information. Mirroring is the most expensive RAID solution, since it re-quires the most disks.

Bit-Interleaved Parity (RAID 3)

The cost of higher availability can be reduced to 1/N, where N is the number of disks in a protection group. Rather than have a complete copy of the original data for each disk, we need only add enough redundant information to restore the lost information on a failure. Reads or writes go to all disks in the group, with one extra disk to hold the check information in case there is a failure.

Block-Interleaved Parity and Distributed Block-Interleaved Parity

(RAID 4 and RAID 5)

Both these levels use the same ratio of data disks and check disks as RAID 3, but they access data differently. The parity is stored as blocks and associated with a set of data blocks.

Since error-detection information in each

sector is checked on reads to see if data is correct, such “small reads” to each disk can occur independently as long as the minimum access is one sector. Writes are another matter. It would seem that each small write would demand that all other disks be accessed to read the rest of the information needed to recalculate the new parity. A “small write” would require reading the old data and old parity, adding the new information, and then writing the new parity to the parity disk and the new data to the data disk.

P+Q redundancy (RAID 6)Parity based schemes protect against a single, self-identifying failures. When a single failure is not suf?cient, parity can be generalized to have a second calculation over the data and another check disk of information. Yet another parity block

is added to allow recovery from a second failure. Thus, the storage overhead is twice that of RAID 5.

Types of storage devices

2013-01-04T21:06:00.003-08:00

Most commonly found storages devices are magnetic disks, magnetic tapes, automated tape libraries, CDs, and DVDs

Magnetic Disks

Despite of new technologies, magnetic disks have dominated nonvolatile storage since 1965. Magnetic disks play two roles in computer systems:

Long-term, nonvolatile storage for files, even when no programs are running
A level of the memory hierarchy below main memory used as a backing store

for virtual memory during program execution

.A magnetic disk consists of a collection of platters (generally 1 to 12), rotating on a spindle at 3,600 to 15,000 revolutions per minute (RPM). Traditionally, the biggest disks have the highest performance and the smallest disks have the lowest price per disk drive.

The disk surface is divided into concentric circles, designated tracks. In the past, all tracks had the same number of sectors; the outer tracks, which are longer, recorded information at a much lower density than the inner tracks.Recording more sectors on the outer tracks than on the inner tracks, called constant bit density.. This name is misleading, as the bit density is not really constant. Typically, the inner tracks are recorded at the highest density and the outer tracks at the lowest, but the outer tracks might record, say, 1.7 times more bits despite being 2.1 times longer.

To read and write information into a sector, a movable arm containing a read/ write head is located over each surface . The term cylinder is used to refer to all the tracks under the arms at a given point on all surfaces.

To read or write a sector, the disk controller sends a command to move the arm

over the proper track. This operation is called a seek, and the time to move the arm to the desired track is called seek time.

Average seek time is the subject of considerable misunderstanding. Disk manufacturers report minimum seek time, maximum seek time, and average seek time in their manuals. The first two are easy to measure, but the average was open to wide interpretation. The industry decided to calculate average seek time as the sum of the time for all possible seeks divided by the number of possible seeks.

Optical Disks

One challenger to magnetic disks is optical compact disks, or CDs, and its successor, called Digital Video Discs and then Digital Versatile Discs or just DVDs. Both the CD-ROM and DVD-ROM are removable and inexpensive to manufacture, but they are read-only mediums. These 4.7-inch diameter disks hold 0.65 and 4.7 GB, respectively, although some DVDs write on both sides to double their capacity. Their high capacity and low cost have led to CD-ROMs and DVDROMs replacing floppy disks as the favorite medium for distributing software and other types of computer data. They are also write-once and rewritable DVDs, called DVD-R and (alas) DVDRAM. Rewritable DVD drives cost ten times as much as DVD-ROM drives.

Magnetic Tapes

Magnetic tapes have been part of computer systems as long as disks because they use the similar technology as disks, and hence historically have followed the same density improvements. The inherent cost/performance difference between disks and tapes is based on their geometries:

1. Fixed rotating platters offer random access in milliseconds, but disks have a limited storage area and the storage medium is sealed within each reader.

2. Long strips wound on removable spools of “unlimited” length mean many tapes can be used per reader, but tapes require sequential access that can take seconds.

One of the limits of tapes had been the speed at which the tapes can spin without breaking or jamming. A technology called helical scan tapes solves this problem by keeping the tape speed the same but recording the information on a diagonal to the tape with a tape reader that spins much faster than the tape is moving. This technology increases recording density by about a factor of 20 to 50. Helical scan tapes were developed for low-cost VCRs and camcorders, which brought down the cost of the tapes and readers.

One drawback to tapes is that they wear out; Helical tapes last for hundreds of passes, while the traditional longitudinal tapes wear out in thousands to millions of passes.

Automated Tape Libraries

Tape capacities are enhanced by inexpensive robots to automatically load and store tapes, offering a new level of storage hierarchy. These near line tapes mean access to terabytes of information in tens of seconds, without the intervention of a human operator

Flash Memory

Embedded devices also need nonvolatile storage, but premiums placed on space and power normally lead to the use of Flash ing. Flash memory is also used as a rewritable ROM in embedded system, typically to allow software to be upgraded without having to replace chips.

Applications are typically prohibited from writing to flash memory in such circumstances.

Like electrically erasable and programmable read-only memories (EEPROM). Compared to disks, Flash memories offer low power consumption (less than 50 mill watts), can be sold in small sizes, and offer read access times comparable to DRAMs.

Memory technology

2013-01-04T21:06:00.001-08:00

Memory latency is traditionally quoted using two measures—access time and cycle time. Access time is the time between when a read is requested and when the desired word arrives, cycle time is the minimum time between requests to memory. One reason that cycle time is greater than access time is that the memory needs the address lines to be stable between accesses.

DRAM technology

The main memory of virtually every desktop or server computer sold since 1975 is composed of semiconductor DRAMs,. As early DRAMs grew in capacity, the cost of a package with all the necessary address lines was an issue. The solution was to multiplex the address lines, thereby

cutting the number of address pins in half. One half of the address is sent first, called the row access strobe or(RAS). It is followed by the other half of the address, sent during the column access strobe(CAS). These names come from the internal chip organization, since the memory is organized as a rectangular matrix addressed by rows and columns.

Although we have been talking about individual chips, DRAMs are commonly sold on small boards called DIMMs for Dual Inline Memory Modules. DIMMs typically contain 4 to 16 DRAMs. They are normally organized to be eight bytes wide for desktop systems. In addition to the DIMM packaging and the new interfaces to improve the data transfer time, discussed in the following subsections, the biggest change to DRAMs has been a slowing down in capacity growth.

SRAM Technology

In contrast to DRAMs are SRAMs—the first letter standing for static. The dynamic nature of the circuits in DRAM require data to be written back after being read, hence the difference between the access time and the cycle time as well as the need to refresh. SRAMs typically use six transistors per bit to prevent the information from being disturbed when read.

In DRAM designs the emphasis is on cost per bit and capacity, while SRAM designs are concerned with speed and capacity. (Because of this concern, SRAM address lines are not multiplexed.). Thus, unlike DRAMs, there is no difference between access time and cycle time. For memories designed in comparable technologies, the capacity of DRAMs is roughly 4 to 8 times that of SRAMs. The cycle time of SRAMs is 8 to 16 times faster than DRAMs, but they are also 8 to 16 times as expensive.

Embedded Processor Memory Technology: ROM and Flash

Embedded computers usually have small memories, and most do not have a disk to act as non-volatile storage. Two memory technologies are found in embedded computers to address this problem.

The first is Read-Only Memory (ROM). ROM is programmed at time of manufacture, needing only a single transistor per bit to represent 1 or 0. ROM is used for the embedded program and for constants, often included as part of a larger chip.

In addition to being non-volatile, ROM is also non-destructible; nothing the computer can do can modify the contents of this memory. Hence, ROM also provides a level of protection to the code of embedded computers. Since address based protection is often not enabled in embedded processors, ROM can fulfill an important role.

The second memory technology offers non-volatility but allows the memory to be modified. Flash memory allows the embedded device to alter nonvolatile memory after the system is manufactured, which can shorten product development.

Improving Memory Performance in a standard DRAM Chip

To improve bandwidth, there have been a variety of evolutionary innovations over time.

1. The first was timing signals that allow repeated accesses to the row buffer without another row access time, typically called fast page mode..

2. The second major change is that conventional DRAMs have an asynchronousinterface to the memory controller, and hence every transfer involves overhead to synchronize with the controller.This optimization is called Synchronous DRAM( SDRAM).

3. The third major DRAM innovation to increase bandwidth is to transfer data onboth the rising edge and falling edge of the DRAM clock signal, thereby doubling the peak data rate. This optimization is calledDouble Data Rate(DDR).

Main memory and performance

2013-01-04T21:05:00.005-08:00

Main memory satisfies the demands of caches and serves as the I/O interface. And it is the destination of inputs well as the source for output. Performance measures of main memory emphasize both latency and bandwidth. (Memory bandwidth is the number of bytes read or written per unit time), The main memory affects the cache miss penalty, is the primary concern of the cache. While main memory bandwidth is the primary concern of I/O and multiprocessors.

Although caches are interested in low latency memory, it is generally easier to improve memory bandwidth with new organizations than it is to reduce latency.With the popularity of second-level caches and their larger block sizes, main memory bandwidth becomes important to caches as well. In fact, cache designers increase block size to take advantage of the high memory bandwidth.

First Technique for Higher Bandwidth: Wider Main Memory

First-level caches are often organized with a physical width of one word because most CPU accesses are that size. Doubling or quadrupling the width of the cache and the memory will double or quadruple the memory bandwidth. There is cost in the wider connection between the CPU and memory, typically called a memory bus. CPUs will still access the cache a word at a time, so there now needs to be a multiplexor between the cache and the CPU—and that multiplexor may be on the critical timing path. Second-level caches can help since the multiplexing can be between first- and second-level caches, not on the critical path.

Disadvantages:

Since main memory is traditionally expandable by the customer, a drawback to wide memory is that the minimum increment is doubled or quadrupled when the width is doubled or quadrupled. In addition, memories with error correction have difficulties with writes to a portion of the protected block, such as a byte. The rest of the data must be read so that the new error correction code can be calculated and stored when the data are written.

Second Technique for Higher Bandwidth: Simple Interleaved Memory

Increasing width is one way to improve bandwidth, but another is to take advantage of the potential parallelism of having many chips in a memory system. Memory chips can be organized in banks to read or write multiple words at a time rather than a single word. In general, the purpose of interleaved memory is to try to take advantage of the potential memory bandwidth of all the chips in the system .In contrast, most memory systems activate only the chips containing the needed words.

This mapping is referred to as the interleaving factor; interleaved memory normally means banks of memory that are word interleaved. This interleaving optimizes sequential memory accesses. A cache read miss is an ideal match to word-interleaved memory, as the words in a block are read sequentially.

How many banks should be included? One metric, used in vector computers, is as follows: Number of banks = Number of clock cycles to access word in bank

Disadvantages:

1. Shrinking number of chips is the main disadvantage of interleaved memory banks.

2. Second disadvantage of memory banks is again the difficulty of main memory expansion. Either the memory system must support multiple generations of memory chips, or the memory controller changes the interleaving based on the size of physical memory, or both.

Third Technique for Higher Bandwidth: Independent Memory Banks

The original motivation for memory banks was higher memory bandwidth by interleaving sequential accesses. This hardware is not much more difficult since the banks can share address lines with a memory controller, enabling each bank to use the data portion of the memory bus.

A generalization of interleaving is to allow multiple independent accesses, where multiple memory controllers allow banks to operate independently. Each bank needs separate address lines and possibly a separate data bus

Independent of memory technology, higher bandwidth is available using memory banks, by making memory and its bus wider, or doing both.

Reducing hit time

2013-01-04T21:05:00.002-08:00

First Hit Time Reduction: Small and Simple Caches to Reduce Hit Time

· A time-consuming portion of a cache hit is using the index portion of the address to read the tag memory and then compare it to the address. Smaller hardware can be faster, so a small cache can help the hit time. It is also critical to keep an L2 cache small enough to fit on the same chip as the processor to avoid the time penalty of going off chip.

· The second suggestion is to keep the cache simple, such as using direct mapping. One benefit of direct-mapped caches is that the designer can overlap the tag check with the transmission of the data. This effectively reduces hit time.

· The pressure of a fast clock cycle encourages small and simple cache designs for first-level caches.

· For lower-level caches, some designs strike a compromise by keeping the tags on chip and the data off chip, promising a fast tag check, yet providing the greater capacity of separate memory chips.

· Although the amount of on-chip cache increased with new generations of microprocessors, the size of the L1 caches has recently not increased between

generations.

· The L1 caches are the same size for three generations of AMD microprocessors: K6, Athlon, and Opteron. The emphasis is on fast clock rate while hiding L1 misses with dynamic execution and using L2 caches to avoid going to memory.

Second Hit time Reduction: Way Prediction to Reduce Hit Time

· In way prediction, extra bits are kept in the cache to predict the way, or block within the set of the next cache access.

· This prediction means the multiplexor is set early to select the desired block, and only a single tag comparison is performed that clock cycle in parallel with reading the cache data. A miss results in checking the other blocks for matches in the next clock cycle.

· Added to each block of a cache are block predictor bits. The bits select which of the blocks to try on the access latency is the fast hit time.

· If not, it tries the other block, changes the waypredictor, and has a latency of one extra clock cycle.

· Simulations suggested setprediction accuracy is in excess of 85% for a two-way set, so way prediction saves pipeline stages more than 85% of the time.

· Way prediction is a good match to speculative processors, since they must already undo actions when speculation is unsuccessful. The Pentium 4 uses way prediction.

Third Hit Time Reduction: Trace Caches to Reduce Hit Time

· A challenge in the effort to find lots of instruction-level parallelism is to find

enough instructions every cycle without use dependencies.

· To address this challenge, blocks in a trace cache contain dynamic traces of the executed instructions rather than static sequences of instructions as determined by layout in memory.

· Hence, the branch prediction is folded into the cache and must be validated along with the addresses to have a valid fetch.

· Trace caches have much more complicated address-mapping mechanisms, as the addresses are no longer aligned to power-of-two multiples of the word size. However, they can better utilize long blocks in the instruction cache.

· The downside of trace caches is that conditional branches making different choices result in the same instructions being part of separate traces, which each occupy space in the trace cache and lower its space efficiency.

· Many optimizations are simple to understand and are widely used, but a trace cache is neither simple nor popular.

· It is relatively expensive in area, power, and complexity compared to its benefits, so we believe trace caches are likely a one time innovation. We include them because they appear in the popular Pentium 4.

Fourth Hit Time Reduction: Pipelined Cache Access to Increase Cache Bandwidth

· This optimization is simply to pipeline cache access so that the effective latency

of a first-level cache hit can be multiple clock cycles, giving fast clock cycle time

and high bandwidth but slow hits.

· For example, the pipeline for the Pentium took 1 clock cycle to access the instruction cache, for the Pentium Pro through Pentium III it took 2 clocks, and for the Pentium 4 it takes 4 clocks.

· This split increases the number of pipeline stages, leading to greater penalty on mispredicted branches and more clock cycles between the issue of the load and the useof the data

Reducing cache miss penalty and miss rate

2013-01-04T21:04:00.006-08:00

Reducing Cache Miss Penalty

First Miss Penalty Reduction Technique: Multi-Level Caches

Many techniques to reduce miss penalty affect the CPU. This technique ignores

the CPU, concentrating on the interface between the cache and main memory.

· The first-level cache can be small enough to match the clock cycle time of the fast CPU.

· The second-level cache can be large enough to capture many accesses that would go to main memory, there by lessening the effective miss penalty.

L1 and L2 to refer respectively, to a first-level and a second-level cache, the original formula is

Average memory access time = Hit timeL1 + Miss rateL1 ??Miss penaltyL1

Miss penaltyL1=Hit time L2+Miss rateL2-Miss penaltyL2

Average memory access time = Hit timeL1 + Miss rateL1 ???Hit time _L2+Miss rate_L2* Miss penalty_L2)

· Local miss rate—This rate is simply the number of misses in a cache divided

by the total number of memory accesses to this cache. As you would expect,

for the first-level cache it is equal to Miss rateL1 and for the second-level cache

it is Miss rateL2.

· Global miss rate—The number of misses in the cache divided by the total number

of memory accesses generated by the CPU. Using the terms above, the

global miss rate for the first-level cache is still just Miss rateL1 but for the second-

level cache it is Miss rateL1 ??Miss rateL2.

Average memory stalls per instruction = Misses per instruction_L1*Hit time_L2 + Misses per instruction_{L2 *}Miss penalty_L2.

Second Miss Penalty Reduction Technique: Critical Word First and Early Restart

· Critical word first—Request the missed word first from memory and send it to

the CPU as soon as it arrives; let the CPU continue execution while filling the

rest of the words in the block. Critical-word-first fetch is also called

fetch and requested word first

· Early restart—Fetch the words in normal order, but as soon as the requested

word of the block arrives, send it to the CPU and let the CPU continue execution.

Third Miss Penalty Reduction Technique: Giving Priority to Read Misses over Writes

· This optimization serves reads before writes have been completed.

· Write buffers, however, do complicate memory accesses in that they might hold the updated value of a location needed on a read miss.

· The alternative is to check the contents of the write buffer on a read miss, and if there are no conflicts and the memory system is available,

· The cost of writes by the processor in a write-back cache can also be reduced.

Suppose a read miss will replace a dirty memory block. Instead of writing the

dirty block to memory, and then reading memory, we could copy the dirty block

to a buffer, then read memory, and for which the processor is probably waiting, will

finish sooner.

· Similar to the situation above, if a read miss occurs, the processor can either

stall until the buffers empty or check the addresses of the words in the buffer for conflicts.

Fourth Miss Penalty Reduction Technique: Merging Write Buffer

· This technique also involves write buffers, this time improving their efficiency. Write through caches rely on write buffers, as all stores must be sent to the next lower level of the hierarchy.

· As mentioned above, even write back caches use a simple buffer when a block is replaced. If the write buffer is empty, the data and the full address are written in the buffer

· The write is finished from the CPU's perspective; the CPU continues working while the write buffer prepares to write the word to memory. If the buffer contains other modified blocks, the addresses can be checked to see if the address of this new data matches the address of the valid write buffer entry.

· If so, the new data are combined with that entry called write merging

· If the buffer is full and there is no address match, the cache (and CPU) must wait until the buffer has an empty entry. This optimization uses the memory more efficiently since multiword writes are usually faster than writes performed one word at time.

Fifth Miss Penalty Reduction Technique: Victim Caches

· One approach to lower miss penalty is to remember what was discarded in case it is needed again. Since the discarded data has already been fetched, it can be used again at small cost.

· Such recycling requires a small, fully associative cache between a cache and its refill path. This only blocks that are discarded from a cache because of a miss-victim-and are checked on a miss to see if they have the desired data before going to the next lower-level memory.

· If it is found there, the victim block and cache block are swapped.

· Depending on the program, a four-entry victim cache might remove one quarter of the misses in a 4-KB direct-mapped data cache.

Reducing Miss Rate

We first start with a model that sorts all misses into three simple categories:

· Compulsory—The very first access to a block cannot be in the cache, so the block must be brought into the cache. These are also called cold start misses or first reference misses or first reference misses

· Capacity—If the cache cannot contain all the blocks needed during execution

of a program, capacity misses (in addition to compulsory misses) will occur be-

cause of blocks being discarded and later retrieved.

· Conflict—If the block placement strategy is set associative or direct mapped,

conflict misses will occur be cause a block may be discarded and later retrieved if too many blocks map to its set. These misses are also called collision misses or interference misses

First Miss Rate Reduction Technique: Larger Block Size

· The simplest way to reduce miss rate is to increase the block size.

· Larger block sizes will reduce compulsory misses.

· This reduction occurs because the principle of locality has two components: temporal locality, spatial locality.

· Larger blocks take advantage of spatial locality.

· At the same time, larger blocks increase the miss penalty. Since they reduce

the number of blocks in the cache, larger blocks may increase conflict misses and

even capacity misses if the cache is small.

Second Miss Rate Reduction Technique: Larger caches

The obvious drawback is longer hit time and higher cost. This technique has been especially popular in off-chip caches: The size of second or third level caches in 2001 equals the size of main memory in desktop computers .

Third Miss Rate Reduction Technique: Higher Associativity

There are two general rules of thumb .

· The first is that eight-way set associative is for practical purposes as effective in reducing misses for these sized caches as fully associative. You can see the difference by comparing the 8-way entries to the capacity miss column since capacity misses are calculated using fully associative cache.

· The second observation, called the 2:1 cache rule of thumb and found on the front inside cover, is that a direct-mapped cache of size has about the same miss rate as a 2-way set-

associative cache of size /2. This held for cache sizes less than 128 KB.

· Like many of these examples, improving one aspect of the average memory access time comes at the expense of another. Increasing block size reduced miss rate while increasing miss penalty, and greater associativity can come at the cost of increased hit time

· Hence, the pressure of a fast processor clock cycle encourages simple cache designs, but the increasing miss penalty rewards associativity, as the following example suggests.

Fourth Miss Rate Reduction Technique: Way Prediction and Pseudo-Associative Caches

· In way-prediction, extra bits are kept in the cache to predict cache access. This prediction means the multiplexor is set early to select the desired set, and only a single tag comparison is performed that clockcycle. A miss results in checking the other sets for matches in subsequent clock cycles.

· A related approach is called pseudo-associative or column associative

· Accesses proceed just as in the direct-mapped cache for a hit. On a miss, however,before going to the next lower level of the memory hierarchy, a second cache entry is checked to see if it matches there. A simple way is to invert the most significant bit of the index field to find the other block in the pseudo set.

· Pseudo-associative caches then have one fast and one slow hit time corresponding to a regular hit and a pseudo hit in addition to the miss penalty.

· The performance would then be degraded by this optimization. Hence, it is important to indicate for each set which block should be the fast hit and which should be the slow one. One way is simply to make the upper one fast and swap the contents of the blocks. Another danger is that the miss penalty may become slightly longer, adding the time to check another cache entry.

Fifth Miss Rate Reduction Technique: Compiler Optimizations

Code and Data Rearrangement

· Code can easily be rearranged without affecting correctness; for example,reordering the procedures of a program might reduce instruction miss rates by reducing conflict misses. Reordering the instructions reduced misses by 50% for a 2-KB direct-mapped instruction cache with 4 byte blocks, and by 75% in an 8-KB cache.

· Another code optimization aims for better efficiency from long cache blocks.Aligning basic blocks so that the entry point is at the beginning of a cache block decreases the chance of a cache miss for sequential code.

· Data have even fewer restrictions on location than code. The goal of such transformations is to try to improve the spatial and temporal locality of the data.

· For example, array calculations can be changed to operate on all the data in a cache block rather than blindly striding through arrays in the order the programmer happened to place the loop.

Loop Interchange

· Some programs have nested loops that access data in memory in non sequential order.

· Simply exchanging the nesting of the loops can make the code access the data in the order it is stored.

· Assuming the arrays do not fit in cache, this technique reduces misses by improving spatial locality; reordering maximizes use of data in a cache block before it is discarded.

/* Before */

for (j = 0; j \< 100; j = j+1)

for (i = 0; i \< 5000; i = i+1)

x\[i]\[j] = 2 * x\[i]\[j];

/* After */

for (i = 0; i \< 5000; i = i+1)

for (j = 0; j \< 100; j = j+1)

x\[i]\[j] = 2 * x\[i]\[j];

· The original code would skip through memory in strides of 100 words, while the

revised version accesses all the words in one cache block before going to the next

block.

· This optimization improves cache performance without affecting the number of instructions executed, unlike the prior example.

Blocking

· This optimization tries to reduce misses via improved temporal locality. We are again dealing with multiple arrays, with some arrays accessed by rows and someby columns.

· Storing the arrays row by row (row major order) or column by column (column major order) does not solve the problem because both rows and columns are used in every iteration of the loop. Such orthogonal accesses mean the transformations such as loop interchange are not helpful.

· Instead of operating on entire rows or columns of an array, blocked algorithms

operate on submatrices or blocks.

· The goal is to maximize accesses to the data loaded into the cache before the data are replaced. The code example below,which performs matrix multiplication, helps motivate the optimization:

/* Before */

for (i = 0; i < N; i = i+1)

for (j = 0; j < N; j = j+1)

{

r = 0;

for (k = 0; k < N; k = k + 1)

r = r + y[i][k]*z[k][j];

x[i][j] = r;

};

· The two inner loops read all by elements of z, read the same elements in a row of y

repeatedly, and write one row of elements of x.

· The number of capacity misses clearly depends on and the size of the cache.If it can hold all three N by N . If the cache can hold one N by N matrix and one row of N ,then atleast the i th row of y and the array z may stay in the cache.

Reducing Cache Miss Penalty or Miss Rate via Parallelism

First Miss penalty/Rate Reduction technique: Nonblocking Caches to Increase Cache Bandwidth

· For pipelined computers that allow out-of-order completion , the processor need not stall on a data cache miss.

· For example, the processor could continue fetching instructions from the instruction cache while waiting for the datacache to return the missing data.

· A nonblocking cache or lockup-free cache escalates the potential benefits of such a scheme by allowing the data cache to continue to supply cache hits during a miss.

· This “hit under miss” optimization reduces the effective miss penalty by being helpful during a miss instead of ignoring the requests of the processor.

· A subtle and complex option is that the cache may further lower the effective miss penalty if it can overlap multiple misses: a “hit under multiple miss or miss under miss” optimization. The sec-ond option is beneficial only if the memory system can service multiple misses.

· The real difficulty with performance evaluation of nonblocking caches is that a cache miss does not necessarily stall the processor. In this case, it is difficult to judge the impact of any single miss, and hence difficult to calculate the average memory access time.

Second Miss penalty/Rate Reduction technique: Hardware Prefetching of Instructions and Data to Reduce Miss Penalty or Miss Rate

· Nonblocking caches effectively reduce the miss penalty by overlapping execution with memory access.

· Another approach is to prefetch items before the processor requests them. Both instructions and data can be prefetched, either directly into the caches or into an external buffer that can be more quickly accessed than main memory.

· Instruction prefetch is frequently done in hardware outside of the cache.

· Typically, the processor fetches two blocks on a miss: the requested block and the next consecutive block.

· The requested block is placed in the instruction cache when it returns, and the prefetched block is placed into the instruction stream buffer. If the requested block is present in the instruction stream buffer, the original cache request is canceled, the block is read from the stream buffer, and the

next prefetch request is issued.

Third Miss penalty/Rate Reduction technique: Compiler-Controlled Prefetching to Reduce Miss Penalty or Miss Rate

· Register prefetch will load the value into a register.

· Cache prefetch loads data only into the cache and not the register.

Cache performance

2013-01-04T21:04:00.003-08:00

UNIT V

A better measure of memory-hierarchy performance is the average memory access time:

Average memory access time = Hit time + Miss rate ??Miss penalty

Hit time is the time to hit in the cache.

The components of average access time can be measured either in absolute time say 0.25 to 1.0 nanoseconds on a hit or in the number of clock cycles that the CPU waits for the memory such as a miss penalty of 75 to 100 clock cycles.

Average memory access time and Processor Performance

· First, there are other reasons for stalls, such as contention due to I/O devices using memory.

· Designers often assume that all memory stalls are due to cache misses, since the memory hierarchy typically dominates other reasons for stalls.

· We use this simplifying assumption here, but beware to account for all memory stalls when calculating final performance.

· Second, The CPU stalls during misses, and the memory stall time is strongly correlated to average memory access time.

CPU time = (CPU execution clock cycles + Memory stall clock cycles) ??Clock cycle time

Miss Penalty and Out-of-Order Execution Processors

Let’s redefine memory stalls to lead to a new definition of miss penalty as nonoverlapped latency:

(Memory stall cycles/Instruction)=(Misses/Instruction)*(Total miss latency-Overlapped miss latency)

This equation could be further expanded to account for contention for memory resources in an out-of-order processor by dividing total miss latency into latency without contention and latency due to contention.

Let’s just concentrate on miss latency.

We now have to decide

· length of memory latency: what to consider as the start and the end of a memory

operation in an out-of-order processor.

· length of latency overlap: what is the start of overlap with for the processor (or

equivalently, when do we say a memory operation is stalling the processor).

Improving Cache Performance

The cache optimizations is of four categories:

· Reducing the miss penalty : multilevel caches, critical word first read miss before write miss, merging write buffers, victim caches;

· Reducing the miss rate : larger block size, larger cache size, higher associativity, pseudo-associativity, and compiler optimizations;

· Reducing the miss penalty or miss rate via parallelism : nonblocking caches, hardware prefetching, and compiler prefetching;

· Reducing the time to hit in the cache : small and simple caches,avoiding address translation, and pipelined cache access, and tace caches

Case Study Snooping Coherence Protocol Implementation

2013-01-04T21:03:00.003-08:00

The snooping coherence describe coherence at an abstract level, but hide many essential details and implicitly assume atomic access to the shared bus to provide correct operation. High-performance snooping systems use one or more pipelined, switched interconnects that greatly

improve bandwidth but introduce significant complexity due to transient states and nonatomic transactions. This case study examines a high-performance snooping system, loosely modeled on the Sun E6800, where multiple processor and memory nodes are connected by separate switched address and data networks.

The system organization (middle) with enlargements of a single processor node (left) and a memory module (right). Like most high performance shared-memory systems, this system provides multiple memory modules to increase memory bandwidth. The processor nodes contain a CPU, cache, and a cache controller that implements the coherence protocol. The CPU issues read and write requests to the cache controller over the REQUEST bus and sends/receives data over the DATA bus. The cache controller services these requests locally, (i.e., on cache hits) and on a miss issues a coherence request (e.g., GetShared to request a read-only copy, GetModified to get an exclusive copy) by sending it to the address network via the ADDR_OUT queue. The address network uses a broadcast tree to make sure that all nodes see all coherence

requests in a total order. All nodes, including the requesting node, receive this request in the same order (but not necessarily the same cycle) on the ADDR_IN queue. This total order is essential to ensure that all cache controllers act in concert to maintain coherency. The protocol ensures that at most one node responds, sending a data message on the separate, unordered point-to-point data network

CMP architectures - Design issues

2013-01-04T21:03:00.001-08:00

Chip multiprocessors - also called multi-core microprocessors or CMPs for short - are now the only way to build high-performance microprocessors, for a variety of reasons. Large uniprocessors are no longer scaling in performance, because it is only possible to extract a limited amount of parallelism from a typical instruction stream using conventional superscalar instruction issue techniques. In addition, one cannot simply ratchet up the clock speed on today's processors, or the power dissipation will become prohibitive in all but water-cooled systems. Compounding these problems is the simple fact that with the immense numbers of transistors available on today's microprocessor chips, it is too costly to design and debug ever-larger processors every year or two.

CMPs avoid these problems by filling up a processor die with multiple, relatively simpler processor cores instead of just one huge core. The exact size of a CMP’s cores can vary from very simple pipelines to moderately complex superscalar processors, but once a core has been selected the CMP’s performance can easily scale across silicon process generations simply by stamping down more copies of the hard-to-design, high-speed processor core in each successive chip generation. In addition, parallel code execution, obtained by spreading multiple threads of execution across the various cores, can achieve significantly higher performance than would be possible using only a single core. While parallel threads are already common in many useful workloads, there are still important workloads that are hard to divide into parallel threads. The low inter-processor communication latency between the cores in a CMP helps make a much wider range of applications viable candidates for parallel execution than was possible with conventional, multi-chip multiprocessors; nevertheless, limited parallelism in key applications is

the main factor limiting acceptance of CMPs in some types of systems.

CMPs can best be designed to handle two radically different kinds of workloads that are likely to be used with a CMP: highly parallel, throughput-sensitive applications at one end of the spectrum, and less parallel, latency-sensitive applications at the other. Throughput-sensitive applications, such as server workloads that handle many independent transactions at once, require careful balancing of all parts of a CMP that can limit throughput, such as the individual cores, on-chip cache memory, and off-chip memory interfaces. Several studies and example systems, such as the Sun Niagara, that examine the necessary tradeoffs are presented here. In contrast, latency-sensitive applications — many desktop applications fall into this category — require a focus on reducing inter-core communication latency and applying techniques to help programmers divide their programs into multiple threads as easily as possible. This book discusses many techniques that can be used in CMPs to simplify parallel programming, with an emphasis on research directions proposed at Stanford University. To illustrate the advantages possible with a CMP using a couple of solid examples, extra focus is given to thread-level speculation (TLS), a way to automatically break up nominally sequential applications into parallel threads on a CMP, and transactional memory. This model can greatly simplify manual parallel programming by using hardware — instead of conventional software locks — to enforce atomic code execution of blocks of instructions, a technique that makes parallel coding much less error-prone.

SMT architectures - Design issues

2013-01-04T21:01:00.001-08:00

Simultaneous multithreading (SMT) is a technique for improving CPU performance, where one CPU pretends to be two. The instructions from two threads are interleaved in the CPU pipeline, which can yield a performance gain for two reasons.

The first reason is that modern superscalar procesors have many execution units, and a single thread rarely uses all of them at once.

The second reason is that when a thread stalls because it needs data that is not stored in the cache, the CPU ends up waiting for memory for hundreds of cycles.

In both of these cases, having a second thread immediately ready to run can fill up these empty spaces, and can prevent wasting resources. The important question is how much performance benefit can we expect, and how can we take advantage of it? This is going to become more important as this type of technology is making its way into CPU designs by all the major players: Intel, AMD, IBM and Sun.

According to Intel, SMT (which they call "hyper-threading") can give a performance boost of up to 30%. However, this improvement is application dependant, and there are some applications where hyperthreading actually hurts performance. For example, this DivX encoding benchmark shows a noticable loss when SMT is enabled. This shows that it is not trivial to gain extra performance with SMT. To help shed some light on this question, I found two interesting documents on SMT performance from Intel.

The is about how SMT is the beginning of a shift towards explicit parallelism in all types of applications, not just servers and scientific computation. The last few generations of CPU improvements, such as pipelining and superscalar execution, exploit the implicit parallelism that exists in machine code. Unfortunately, these are hitting the limits of this approach. Sun calls this paradigm shift "throughput computing”. The challenge is that we need to change our tools and mindsets to take advantage of the available multithreaded computational power.

The second gives developers some concrete advice for improving application performance. It describes how to use "cache blocking" effectively on SMT processors. Cache blocking is when you adjust the size of the chunks of data you are processing to fit them into cache. The article presents some interesting graphs which suggest that for a single processor, blocks should be around half to three-quarters the size of the L2 cache, but when hyper-threading is enabled, this size is too big because the cache is shared between two threads. For the best SMT performance, the block size should be between half and a quarter the L2 cache, and it is better to be too small instead of too large. These results also suggest that the operating system needs to be very careful about how it maps threads onto CPUs. The biggest benefit should occur when the two threads share a significant chunk of their working set. Thinking about the problems and the opportunities in this space makes me itching to add multithreading to thttpd. Web serving is naturally a parallel activity, and it would be an interesting challenge to figure out to best scale its single thread of execution to multiple threads. Maybe I need to do my Ph. D. in parallel computing.

Software and hardware multithreading

2013-01-04T21:00:00.004-08:00

The Software Multithreading paradigm has become more popular as efforts to further exploit instruction level parallelism have stalled since the late-1990s. This allowed the concept of Throughput Computing to re-emerge to prominence from the more specialized field of transaction processing:

Even though it is very difficult to further speed up a single thread or single program, most computer systems are actually multi-tasking among multiple threads or programs.
Techniques that would allow speed up of the overall system throughput of all tasks would be a meaningful performance gain.

The two major techniques for throughput computing are multiprocessing and multithreading.

Advantages

Some advantages include:

If a thread gets a lot of cache misses, the other thread(s) can continue, taking advantage of the unused computing resources, which thus can lead to faster overall execution, as these resources would have been idle if only a single thread was executed.
If a thread can not use all the computing resources of the CPU (because instructions depend on each other's result), running another thread permits to not leave these idle.
If several threads work on the same set of data, they can actually share their cache, leading to better cache usage or synchronization on its values.

Hardware multithreading is a well-known technique to increase the utilization of processor resources. The idea is to start executing a different thread when the current thread is stalled. All hardware multithreading schemes assume that the workload consists of several independent tasks.

Basically, three different hardware multithreading techniques can be distinguished: cycle-by-cycle interleaving, block interleaving, and simultaneous multithreading.

In cycle-by-cycle interleaving, the processor switches to a different thread each cycle. In principle, the next instruction of a thread is fed into the pipeline after the retirement of the previous instruction. This eliminates the need for forwarding datapaths, but implies that there must be as many threads as pipeline stages.

In block interleaving also referred to as coarse-grain multithreading, the processor starts executing another thread if the current thread experiences an event that is predicted to have a significantly long latency. If it can be predicted that the latency is larger than the cost of

a thread switch, then the processor can at least hide part of the latency by executing another thread.

Both cycle-by-cycle interleaving as well as block interleaving attempt to eliminate vertical waste. Vertical waste means that no instructions are issued during a cycle because the current thread is stalled. Simultaneous multithreading (SMT) also tries to eliminate horizontal waste (unused instruction slots in a cycle) because it fetches and issues instructions from different threads simultaneously.

Models of memory consistency

2013-01-04T21:00:00.002-08:00

Cache coherence ensures that multiple processors see a consistent view of memory. It does not answer the question of how consistent the view of memory must be. By “how consistent” we mean, when must a processor see a value that has been updated by another processor? Since processors communicate through shared variables (used both for data values and for synchronization), the question boils down to this: In what order must a processor observe the data writes of another processor? Since the only way to “observe the writes of another processor” is through reads, the question becomes, What properties must be enforced among reads and writes to different locations by different processors?

Although the question of how consistent memory must be seems simple, it is remarkably complicated, as we can see with a simple example. Here are two code segments from processes P1 and P2, shown side by side:

1: A = 0; P2: B = 0;

..... .....

A = 1; B = 1;

L1: if (B == 0) ... L2: if (A == 0)...

Assume that the processes are running on different processors, and that locations A and B are originally cached by both processors with the initial value of 0. The most straightforward model for memory consistency is called sequential consistency.

Sequential consistency requires that the result of any execution be the same as if the memory accesses executed by each processor were kept in order and the accesses among different processors were arbitrarily interleaved.

Sequential consistency eliminates the possibility of some no obvious execution in the previous example because the assignments must be completed before the if statements are initiated.

The simplest way to implement sequential consistency is to require a processor to delay the completion of any memory access until all the invalidations caused by that access are completed.

Of course, it is equally effective to delay the next memory access until the previous one is completed.

Remember that memory consistency involves operations among different variables: the two accesses that must be ordered are actually to different memory locations. In our example, we must delay the read of A or B (A == 0 or B == 0) until the previous write has completed (B = 1 or A = 1). Under sequential consistency, we cannot, for example, simply place the write in a write buffer and continue with the read.

The Programmer’s View

Although the sequential consistency model has a performance disadvantage, from the viewpoint of the programmer it has the advantage of simplicity.

The challenge is to develop a programming model that is simple to explain and yet allows a high-performance implementation.

One such programming model that allows us to have a more efficient implementations to assume that programs are synchronized.

A program is synchronized if all access to shared data are ordered by synchronization operations.

A data reference is ordered by a synchronization operation if, in every possible execution, a write of a variable by one processor and an access (either a read or a

write) of that variable by another processor are separated by a pair of synchronization executed before the access by the second processor.

Cases where variables maybe updated without ordering by synchronization are called data races because the execution outcome depends on the relative speed of the processors, and like races in hardware design, the outcome is unpredictable, which leads to another name for synchronized programs: data-race-free.

It is a broadly accepted observation that most programs are synchronized. This observation is true primarily because if the accesses were unsynchronized, the behavior of the program would likely be unpredictable because the speed of execution would determine which processor won a data race and thus affect the results of the program.

Even with sequential consistency, reasoning about such programs is very difficult. Programmers could attempt to guarantee ordering by constructing their own synchronization mechanisms, but this is extremely tricky, can lead to buggy programs, and may not be supported architecturally, meaning that they may not work in future generations of the multiprocessor.

Instead, almost all programmers will choose to use synchronization libraries that are correct and optimized for the multiprocessor and the type of synchronization.

Finally, the use of standard synchronization primitives ensures that even if the architecture implements a more relaxed consistency model than sequential consistency, a synchronized program will behave as if the hardware implemented sequential consistency operations, one executed after the write by the writing processor and one

Relaxed Consistency Models: The Basics

The key idea in relaxed consistency models is to allow reads and writes to complet out of order, but to use synchronization operations to enforce ordering, so that a synchronized program behaves as if the processor were sequentially consistent. There are a variety of relaxed models that are classified according to what read and write orderings they relax.

We specify the orderings by a set of rules of the form X?Y, meaning that operation X must complete before operation Y is done.

Sequential consistency requires maintaining all four possible orderings: R?W, R?R, W?R, and W?W. The relaxed models are defined by which of these four sets of orderings they relax:

1. Relaxing the W?R ordering yields a model known as total store ordering or processor consistency. Because this ordering retains ordering among writes, many programs that operate under sequential consistency operate under this model, without additional synchronization

2. Relaxing the W?W ordering yields a model known as partial store order.

3. Relaxing the R?W and R?R orderings yields a variety of models including weak ordering, the PowerPC consistency model, and release consistency, depending on the details of the ordering restrictions and how synchronization operations enforce ordering.

By relaxing these orderings, the processor can possibly obtain significant performance advantages.

There are, however, many complexities in describing relaxed consistency models, including the advantages and complexities of relaxing different orders, defining precisely what it means for a write to complete, and deciding when processors can see values that the processor itself has written.

For more information about the complexities, implementation issues, and performance potential from relaxed models, we highly recommend the excellent tutorial by Adve and Gharachorloo .

Synchronisation issues

2013-01-04T20:59:00.008-08:00