What's different about multiprocessor software? (Part 5) - Embedded.com

What’s different about multiprocessor software? (Part 5)

Quality-of-service (QoS) for processes means that a process will bereliably scheduled periodically with a given amount of computationtime. Scheduling techniques, such as rate monotonic scheduling (RMS ) ,inherently provide process-level QoS; if we use some other schedulingmethods or mix scheduling policies, we must ensure that the processesthat need quality-of-service obtain the level of service they need.

Quality-of-service can bemodeled using three basic concepts. First, a contract specifies theresources that will be provided. The client may propose a set of terms,such as the amount of bandwidth and rate of missed packets, but theserver may counterpropose a different set of terms based on itsavailable resources.

A protocol manages the establishment of the contract and itsimplementation. Third, a scheduler implements the terms of thecontract, setting the sizes of buffers, managing bandwidth, and so on.

Assuming that we run a QoS-friendly scheduling policy, such as RMS,we must also ensure that the QoS processes obtain the resources theyneed to meet their deadlines. QoS methods have been widely studied innetworking and operating systems.

Resource management algorithms that make decisions on-the-fly simplyto avoid deadlock or minimize local scheduling delay are not sufficientto guarantee that the QoS-oriented processes get their resources ontime. Periodic reservation methods can help ensure that resources areavailable when they are required.

As with all middleware, we can use standards to design QoS servicesor to design custom systems. Early approaches concentrated onstandards. The advent of systems-on-chips, and in particularnetworks-on-chips, has led to a new wave of custom QoS designs.

Gill et al. [Gil03] used a scheduling framework that could mix andmatch different scheduling policies. Their Kokyu framework allows thecombination of static priority scheduling, dynamic priority scheduling,and hybrid algorithms.

Figure 6-21 below shows howtheir scheduling system fits into the service stack. They measuredsystem behavior using three policies: rate-monotonic scheduling,leastlaxity first, and a combination of RMS and least-laxity first.They found that the different policies had somewhat differentcharacteristics and that systems that can switch between schedulingpolicies can provide higher levels of service.

Figure6-21 Middleware organization for multiparadigm scheduling. From Gill etal. [Gil03] © 2003 IEEE.

Combaz et al. [Com05] developed a methodology for generating QoSsoftware that can handle both critical and best-effort communication.They use control- theoretic methods to determine a schedule and usecode synthesis to create statically scheduled code to implement theschedule.

As shown in Figure 6-22, below ,the system being controlled (theplant) is under the control of a combination of a quality manager and ascheduler. The controller generates schedules for a given level ofquality and evaluates the feasibility of those schedules to choosewhich schedule to execute.

Figure6-22 QoS management as control.

Given an execution time for the code required to implement the QoSaction, the controller determines the feasibility of the schedulerelative to the deadlines. Different choices for quality result indifferent schedules. Schedules are generated and selected using anonline incremental algorithm.

Ahluwalia et al. [Ahl05] developed a framework for modeling reactivesystems and monitoring those properties using Real-Time CORBA. Theydeveloped an architecture definition language for interaction services.A UML description of the model is shown in Figure 6-23 below with the parts ofthe model specific to interactions shown within the dotted line.

Figure6-23 Interaction domain and system services model. From Ahluwalia etal. [Ah05] © 2005 ACM Press.

The InteractionElement type specifies an interaction, which can beatomic or composite. A set of operators allow interaction elements tobe combined and define the way in which deadlines for the combinationare created from the operand interactions. Operators include seq, par,alt, loop, and join. The code generated from these specificationsincludes monitors that check system operation against specifieddeadlines.

Krishnamurthy et al. [Kri01] developed methods for CORBA-based QoS.The QuO model, shown in Figure 6-24below , uses a variety of mechanisms to managequality-of-service. Contract objects encapsulate the agreement betweenthe client and the system about the level of service to be provided; aquality description language is used to describe these contracts.Delegate objects act as local proxies for remote objects.

System condition objects act as the interface to the parts of theunderlying system that control and measure quality-of-service. Propertymanagers handle the implementation of QoS characteristics for theserver. The object request broker must also be modified to handle theQoS characteristics of the underlying service. Code generators createthe various objects required to implement these functions.

Figure6-24 QuO objects for quality-of-service management.

A notification service provides a publish/subscribe system topropagate events. Gore et al. [Gor01] developed a CORBA notificationservice that supports QoS services. Their system deals with structuredevents that include a domain, type and event name, QoS characteristicsfor the event, and a set of data. The system specification describesseveral QoS properties, including:

Reliability. If reliability is specified and supported, the notification servicemust reconnect and deliver events after a crash.
Priority. It relates to other users of this channel.
Expiration time. The time range in which an event is valid.
Earliestdeliveries time. The first time at which an event can bedelivered.
Maximum events perconsumer. The number of events queued in the channel.
Order policy. The order in which events are buffered for delivery.
Discard policy .A policy for discarding events when queues fill up.

A channel has suppliers and consumers of events. A supplier orconsumer can use push style or pull style. Proxy components exist forthe producer and consumer sides of push and pull services. The eventchannel works with supplier and consumer administrator components tomanage QoS

QoS and Networks on Chip
Networks-on-chips must provide quality-of-service functions to supportmultimedia and other rate-sensitive applications. Because NoCsgenerally do not run the Internet Protocol, they often take advantageof their physical layer to efficiently provide QoS.

The GMRS system [Hua99] provides QoS services in a heterogeneousmultiprocessor. They use the ripple scheduling methodology to negotiateresources. They build a scheduling spanning tree that models theresources along the path required for a QoS-governed communication.

A negotiation and adaptation protocol uses the tree to allocate theresources required to satisfy the QoS request. The protocol firstchecks the path to ensure that the required resources are available. Itthen propagates a commit signal to gather the resources or an abortsignal if so required.

The QNoC network-on-chip [Bol04] provides four levels of service.Signaling is used for urgent, short messages and is given the highestpriority. Real-time service guarantees bandwidth and latency forconnection. Read/write service is similar to a microprocessor busoperaiton and is used for memory and register access. Block-transferservice is used for long transfers, similar to DMA in microprocessorsystems.

Millberg et al. [Mil04b] used looped containers to provide QoS inthe Nostrum network-on-chip. To maintain a spot in the network for thepackets required by the connection, they return messages from receiverback to sender after they are used. At the sender, a packet is loadedwith its data and sent into the network. After reaching thedestination, its data is unloaded and the packet is sent back to itssource.

When it arrives, it can be loaded with new data again. Eachprocessing element runs a distributed system resource manager to handlerequests. These agents can negotiate with each other to checkresources.

The resource management agents may rely on agents that represent theCPU, the network, or other resources on a PE. The structure of theirphysical network ensures that certain combinations of packets will notinterfere with each other. Noninterference plus looped containers allowNostrum to provide several QoS channels in the network.

Design Verification
Verifying software is always a challenge, but verifying multiprocessorsoftware is harder than verifying uniprocessor software for severalreasons:

1) The data of interest maybe harder to observe and/or control.
2) It may be harder to drivecertain parts of the system into desired states.
3) Timing effects are muchharder to generate and test.

Software need not be entirely debugged on the target platform. Someaspects of the software may be properly addressed on other types ofmachines. However, after any porting, the designer must carefullyverify the correctness of any port-specific characteristics. Inaddition, some hidden platform assumptions may not have been tested onthe debugging platform and it may take a large number of tests toexpose them on the target.

Because embedded systems must meet performance, power/energy, andsize constraints, we want to evaluate the software not just forcorrectness but also for these nonfunctional attributes.

Multiprococessor Simulation
We can use multiprocessor simulators, such as cycle-accurate ones,to obtain detailed information about performance and energyconsumption. The next two examples describes a simulator for embeddedmultiprocessors.

Example #1: VastSystems CoMETSimulator. The CoMET simulator [Hel99] is designed to simulatesystems of embedded processors. The processor model used in CoMET, shown in the Figure below is knownas the virtual processor model (VPN). Part of the VPN is built from theapplication code; this custom model reflects the behavior of the codethat can be determined statically.

The other part of the VPN includes parts of the processor that mustbe modeled dynamically: I/O, cache, and so on. This combination ofstatic and dynamic modeling allows the VPN to run at very high speeds.The simulation framework includes a backplane that connects the variousvirtual processor models as well as to hardware models.

Thebackbone system allows several different types of simulators to becombined for cycle-accurate simulation. (Source: From Hellestrand(Hel1999) © 1999 IEEE).

Example #2:The MESH Simulator . MESH [Pau02b] is a heterogeneous systemssimulator that bridges logical and physical time. An event is a pair ofa tag and a value. The tag denotes time; but time may not necessarilybe wall clock time. The behavior of a thread is given by an ordered setof events.

Depending on the level of detail at which the system is modeled, theevents may be mapped onto physical time or onto logical sequences. Insimple cases, a simulation of the logical simulation can be transformedinto a simulation in physical time simply by adding time steps in thelogical sequence.

However, in many cases, the mapping from logical to physicalbehavior is not so simple. MESH models more complex relationshipsbetween logical and physical time using macro events and micro events.Each macro event contains a sequence of micro events, thus establishingthe correspondence between the two notions of time.

Summary
Many of the techniques developed for uniprocessor operating systemsapply to multiprocessors as well. However, multiprocessors areinherently harder because they provide true concurrency, not justapparent concurrency.

It is harder to determine how fast multiprocessor software will run,but it is possible to make accurate estimates. Software stacks helpabstract the underlying platform, but one must be careful not to makethe software layers too inefficient.

To read Part 1, go to Therole of the operating system
To read Part 2, go to Multiprocessor Scheduling.
To read Part 3, go to Event-drivenmultiprocessor scheduling analysis
To read Part 4: go to Services and middleware for embedded multiprocessors

Usedwith the permission of the publisher, Newnes/Elsevier, this series offive articles is based on copyrighted material from “High-PerformanceEmbedded Computing,” by Wayne Wolf. The book can be purchased online.

Wayne Wolf is professor of electricalengineering at PrincetonUniversity. Prior to joining Princeton he was with AT&T BellLaboratories. He has served as editor in chief of the ACM Transactionson Embedded Computing and of DesignAutomation for Embedded Systems

References
[Gil03] Christopher D. Gill, et. al., Multiparadigmschedulingfor distributed real-time embedded computing,” Proceedings of theIEEE,January, 2003
[Com05] Jacques Combaz, et.al., “QoS quality control for optimality and safety,” in Proceedings ofthe Fifth ACM Conference on Embedded Software,” ACM Press, 2005
[Ahl05] Jaswinder Ahluwalia,et. al. “Model-basedrun-time monitoringof end-to-end systems,” in Proceedings of the Fifth ACM ConferenceonEmbedded Software, ACM Press, 2005.
[Kri01] Yamuna Krishnamurthy,et.al., “Integrationof QoS-enabled distributed object computingmiddleware for developing next-generation distributed applications,“inProceedings of the ACM SIGPLAN Workshop on Languages, Compilers, andTools for Embedded Systems, ACM Press, 2001.
[Gor01] Pradeep Gore, et.al.,”Designingand optimizing a scalable  CORBA notification service,”in Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers andTools for Embedded Systems,  ACM Press, 2001
[Hua99] J. Huang, et.al.,  “Ondeveloping distributed middleware services for QoS- andcriticality-based resource negotiation and adaption,” Journal ofReal-Time Systems, 16, 1999.
[Bol04] E. Bolotin, et.al.,  “QNoC:QoS architecture and design process fornetwork-on-chip,” The Journal of Systems Architecture, February,2004.
[Mil04b]   Mikael Millberg,et. al., “Guaranteed bandwith using looped containers in temoprarilydisjointed networks with Nostrum network on chip,” in Proceedingsof the Conference on Design Automation and Test in Eruope, IEEEComputer Society Press, 2004.
[Hel99] Graham  RHellestrand, “Therevolution in systems engineering,” IEEE Spectrum,September, 1999.
[Pau02b] JoAnn Paul and DonaldThomas, “Alayered, co-design virtual machine approach to modelingcomputer systems,” in Proceedings of the Conference on DesignAutomation and Test in Europe,” IEEE Computer Society Press, 2002.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.