comp.lang.ada
 help / color / mirror / Atom feed
* Processor Synchronization
@ 1999-01-19  0:00 Marin David Condic
  1999-01-19  0:00 ` Ken Keys
                   ` (4 more replies)
  0 siblings, 5 replies; 14+ messages in thread
From: Marin David Condic @ 1999-01-19  0:00 UTC (permalink / raw)


I am preparing an in-house class on embedded system executives and I
want to present a comprehensive overview of different designs. One of
the areas I want to cover is processor synchronization. I am looking for
a book or other reference material that discusses techniques for
synchronizing independent processors. Specifically, I am interested in
techniques used when building dual (or multiple) channel systems with
relatively primitive communication between the two channels. (discrete
lines, Manchester data link, etc.) Information pertaining to use of
operating systems (e.g. Unix) and distributed systems may be interesting
but not useful in this case.

The most general description of the problem domain I can come up with is
this: The problem is at power-up, you have to get both processors
ticking off at the same "heartbeat" so that they have the same frame of
reference. Generally, you're going to have N cycles (frames, slots,
whatever your favorite terminology is) and it is important that both
processors be operating on cycle X at the same time. Once running, the
processors have to detect drift in their cycling and correct for this so
that they continue to both start on the same cycle at the same time. We
have done this sort of thing in-house, but I'm looking for a discussion
of a variety of algorithms and some analysis of the strengths &
weaknesses of each.

If anybody has a favorite book, article or web-page on this subject, I
would appreciate hearing about it. Thanks.

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669
***To reply, remove "bogon" from the domain name.***

    "Nobody shot me."

        --  Last words of Frank Gusenberg when asked by police who
            shot him fourteen times with a machine gun in the Saint
            Valentine's Day Massacre.




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-19  0:00 Processor Synchronization Marin David Condic
@ 1999-01-19  0:00 ` Ken Keys
  1999-01-20  0:00   ` Marin David Condic
  1999-01-20  0:00 ` dennison
                   ` (3 subsequent siblings)
  4 siblings, 1 reply; 14+ messages in thread
From: Ken Keys @ 1999-01-19  0:00 UTC (permalink / raw)


Marin David Condic wrote:
 
 > The most general description of the problem domain I can come up with
is
 > this: The problem is at power-up, you have to get both processors
 > ticking off at the same "heartbeat" so that they have the same frame
of
 > reference. Generally, you're going to have N cycles (frames, slots,
 > whatever your favorite terminology is) and it is important that both
 > processors be operating on cycle X at the same time. Once running,
the
 > processors have to detect drift in their cycling and correct for this
so
 > that they continue to both start on the same cycle at the same time.
We
 > have done this sort of thing in-house, but I'm looking for a
discussion
 > of a variety of algorithms and some analysis of the strengths &
 > weaknesses of each.

How did you do it when did it in-house? Did you use an RTC or some other
common (hardware) time reference?

KLK




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-19  0:00 ` Ken Keys
@ 1999-01-20  0:00   ` Marin David Condic
  1999-01-20  0:00     ` Ken Keys
                       ` (2 more replies)
  0 siblings, 3 replies; 14+ messages in thread
From: Marin David Condic @ 1999-01-20  0:00 UTC (permalink / raw)
  To: Ken Keys

Ken Keys wrote:
> 
> How did you do it when did it in-house? Did you use an RTC or some other
> common (hardware) time reference?
> 
We have a cross channel sync discrete that enables the two processors to
signal each other. Each processor has a watchdog timer that ticks off
1ms interrupts to drive the software and the wdt outputs a
synchronization signal at 12.5ms intervals (programmable, of course, but
this is what we use.) The wdt has a restart feature used for
synchronization. So it becomes a matter of each channel looking at the
other guy via the discrete to determine when he is in his 12.5ms frame
and agreeing on who will reset so that they are both in the same frame
at the same time. That gets you into coarse sync. From there, you've got
to execute small delays with a real time counter so that both channels
are at the leading edge of the 12.5ms signal at the same time. Then
you've declared you are "in sync" and the system initialization can
continue on to control active mode. Periodically in the course of
operation, you've got to make fine tuning adjustments to keep yourself
in fine sync. This is again a matter of both channels signaling each
other via the sync discretes.

What I am curious about is if anybody has done any study of algorithms
for this sort of synchronization. I imagine there are methods of doing
synchronization by sharing opinions about what time it is or with other
sorts of semaphore setups and so on. (I know in the radio business
you've got to account for propogation delays and other problems if you
want the radios to sync up. Someone might have some studies of this sort
as well.)

What I'm hoping to do is explain to my class what it is that we do now
for this sort of channel synchronization and then present some
alternatives which might be used in future designs. Would we be better
off if we got our hardware built with a time-of-day clock and traded
opinions on what time it is? Are there other algorithms that work better
at getting things in sync faster and keeping them in sync with less
waste of CPU time? (delays are bad news when you're running real slow
processors and have a 1ms cycle time!) In other words, is someone out
there more clever than ourselves?

If you know of any references or sources of information, I'd appreciate
hearing about them. Thanks.

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669
***To reply, remove "bogon" from the domain name.***

    "Airplanes are interesting toys but of no military value."

        --  Marechal Ferdinand Foch, Professor of Strategy, Ecole
Superieure
            de Guerre.




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-20  0:00   ` Marin David Condic
@ 1999-01-20  0:00     ` Ken Keys
  1999-01-21  0:00       ` Marin David Condic
  1999-01-21  0:00     ` Sune Falck
       [not found]     ` <36a83fe3.3666942@news.geccs.gecm.com>
  2 siblings, 1 reply; 14+ messages in thread
From: Ken Keys @ 1999-01-20  0:00 UTC (permalink / raw)


Marin David Condic wrote:
 > 
 > Ken Keys wrote:
 > >
 > > How did you do it when did it in-house? Did you use an RTC or some
other
 > > common (hardware) time reference?
 > >
 > We have a cross channel sync discrete that enables the two processors
to
 > signal each other. Each processor has a watchdog timer that ticks off
 > 1ms interrupts to drive the software and the wdt outputs a
 > synchronization signal at 12.5ms intervals (programmable, of course,
but
 > this is what we use.) The wdt has a restart feature used for
 > synchronization. So it becomes a matter of each channel looking at
the
 > other guy via the discrete to determine when he is in his 12.5ms
frame
 > and agreeing on who will reset so that they are both in the same
frame
 > at the same time. That gets you into coarse sync. From there, you've
got
 > to execute small delays with a real time counter so that both
channels
 > are at the leading edge of the 12.5ms signal at the same time. Then
 > you've declared you are "in sync" and the system initialization can
 > continue on to control active mode. Periodically in the course of
 > operation, you've got to make fine tuning adjustments to keep
yourself
 > in fine sync. This is again a matter of both channels signaling each
 > other via the sync discretes.
 > 
 > What I am curious about is if anybody has done any study of
algorithms
 > for this sort of synchronization. I imagine there are methods of
doing
 > synchronization by sharing opinions about what time it is or with
other
 > sorts of semaphore setups and so on. (I know in the radio business
 > you've got to account for propogation delays and other problems if
you
 > want the radios to sync up. Someone might have some studies of this
sort
 > as well.)
 > 
 > What I'm hoping to do is explain to my class what it is that we do
now
 > for this sort of channel synchronization and then present some
 > alternatives which might be used in future designs. Would we be
better
 > off if we got our hardware built with a time-of-day clock and traded
 > opinions on what time it is? Are there other algorithms that work
better
 > at getting things in sync faster and keeping them in sync with less
 > waste of CPU time? (delays are bad news when you're running real slow
 > processors and have a 1ms cycle time!) In other words, is someone out
 > there more clever than ourselves?
 > 
 > If you know of any references or sources of information, I'd
appreciate
 > hearing about them. Thanks.
 > 
 > MDC

I have never seen multiple processors coupled that closely. Usually,
processors are tied to some external event through interrupts or
whatever. Where the events themselves are unavailable, the input data
are given a timestamp that is referenced to some common clock--not
necessarily a time of day clock. Sometimes this timestamping requires
you to do some interpolation to get the data to line up as in, for
instance, the case of merging information from a Radar sensor with that
from an IR sensor where there are different amounts of processing delay
and differing update rates. Besides, if the data is coming from
something like a video raster, deciding just where in the elapsed time
covered by that raster the data occurs requires some interpretation.

Are your processors in some kind of redundant voting arrangement where
they are executing the exact same code on the same inputs? If so, that
probably represents a fairly specialized case. You might be able to find
some information on that type of case in some NASA pubs.

KLK




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-19  0:00 Processor Synchronization Marin David Condic
  1999-01-19  0:00 ` Ken Keys
@ 1999-01-20  0:00 ` dennison
  1999-01-21  0:00 ` Peter Jensen
                   ` (2 subsequent siblings)
  4 siblings, 0 replies; 14+ messages in thread
From: dennison @ 1999-01-20  0:00 UTC (permalink / raw)


In article <36A509DB.95F62C0B@pwfl.com>,
  diespammer@pwfl.com wrote:
> I am preparing an in-house class on embedded system executives and I
> want to present a comprehensive overview of different designs. One of
> the areas I want to cover is processor synchronization. I am looking for
> a book or other reference material that discusses techniques for
> synchronizing independent processors. Specifically, I am interested in
> techniques used when building dual (or multiple) channel systems with
> relatively primitive communication between the two channels. (discrete
> lines, Manchester data link, etc.) Information pertaining to use of
> operating systems (e.g. Unix) and distributed systems may be interesting
> but not useful in this case.

Distributed Operating Systems & Algorithms, by Randy Chow and Theodore Johnson
was used in one of my grad-level OS courses. It contains a lot of great
algorithms for coordinating systems in a distributed environment. But I'm not
sure it goes down to the level you are talking about.


T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-20  0:00     ` Ken Keys
@ 1999-01-21  0:00       ` Marin David Condic
  0 siblings, 0 replies; 14+ messages in thread
From: Marin David Condic @ 1999-01-21  0:00 UTC (permalink / raw)


Ken Keys wrote:
> I have never seen multiple processors coupled that closely. Usually,
> processors are tied to some external event through interrupts or
> whatever. Where the events themselves are unavailable, the input data
> are given a timestamp that is referenced to some common clock--not
> necessarily a time of day clock. Sometimes this timestamping requires
> you to do some interpolation to get the data to line up as in, for
> instance, the case of merging information from a Radar sensor with that
> from an IR sensor where there are different amounts of processing delay
> and differing update rates. Besides, if the data is coming from
> something like a video raster, deciding just where in the elapsed time
> covered by that raster the data occurs requires some interpretation.

In this application, you wouldn't want to tie the processors together
with a common interrupt or clock. That creates a single point failure
and the reason for having the two processors is to minimize risk if
something breaks. 

The reason for tightly aligning both channels is because you want them
operating on essentially the same data at the same time so that if one
goes down, the other takes over and there isn't a skipped beat. When
we're reading A/Ds or F/Ds that are monitoring LVDTs or RVDTs or rotor
speeds, data can get old very fast. Loop closure on stale data can get
unstable.

> 
> Are your processors in some kind of redundant voting arrangement where
> they are executing the exact same code on the same inputs? If so, that
> probably represents a fairly specialized case. You might be able to find
> some information on that type of case in some NASA pubs.
> 
The processors are doing exactly what you describe. As to how uncommon
that is, I'm afraid I couldn't say. I know it is fairly common to go
with dual redundant systems in a number of mission critical
applications. The Ariane 5 disaster (please! not that again!) was an
example of the dual redundancy not succeeding, but that hasn't stopped
us from building them that way.

I know that tight synchronization between two or more radios is another
case. Your basic frequency hopping radio (cell phones and classified
military stuff) have to agree pretty accurately on what time it is so
that they can all change frequencies at the same time. (And that's just
about all I want to say on *that* subject in a public forum!)

It may be specialized enough that nobody has done any theoretical
research into various algorithms. I may be SOL in hoping to find
something like this. But it seemed like a good idea to ask and see what
comes up.

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669
***To reply, remove "bogon" from the domain name.***

    "Airplanes are interesting toys but of no military value."

        --  Marechal Ferdinand Foch, Professor of Strategy,
            Ecole Superieure de Guerre.




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-21  0:00     ` Sune Falck
@ 1999-01-21  0:00       ` Marin David Condic
  0 siblings, 0 replies; 14+ messages in thread
From: Marin David Condic @ 1999-01-21  0:00 UTC (permalink / raw)


Sune Falck wrote:
> 
> Just a pointer.
> 
> Digital transmisson systems for telephony have to stay in sync over long
> distances.
> 
> PCM systems such as SONET, SDH (Syncrounous Digital Hiearchy) and PDH
> (Plesiosynconius Digital Hiarchy) are using methods for clock distribution
> and syncronsiation that may be of interest. The time slots occur every 125
> microsecond and they must stay in sync in the whole network.
> 
> /Sune Falck

A long time ago, in a galaxy far, far away - New Jersey, that is to say
- I worked for a company that at the time was called Singer Electronic
Systems. (It changed names two or three times while I worked there. I
don't know who it is now.) We did things similar to this. We regularly
lost people who took jobs at Bell Labs because the skills needed were
similar.

This process of net entry and synchronization is something like what we
do now to sync up both channels of our control. Would you know of any
published material that talks about techniques for net entry - which
isn't classified?

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669
***To reply, remove "bogon" from the domain name.***

    "Airplanes are interesting toys but of no military value."

        --  Marechal Ferdinand Foch, Professor of Strategy,
            Ecole Superieure de Guerre.




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-21  0:00 ` The Bohemian Monk
@ 1999-01-21  0:00   ` Marin David Condic
  1999-01-22  0:00     ` Tom Ziomek
  0 siblings, 1 reply; 14+ messages in thread
From: Marin David Condic @ 1999-01-21  0:00 UTC (permalink / raw)


The Bohemian Monk wrote:
> 
> After reading all the thread ... damn guys wake up.  A processor as
> simple as the 8088 has bus sync signals to allow multiple processors on
> a single buss, or a single memory.  Software does little for
> multiprocessing, hardware does the most, unless you program embedded in
> something like Forth.  With non-buss-master processesors you can use a
> PAL to envoke wait-states based on buss signals, all in hardware with
> simple memory table semaphores for access control.
> 
I'll try not to condescend, but boy is it tempting! :-)

Our style of computer system for jet and rocket engines is not nearly
that easy to do. The requirements won't allow for it. This box is
strapped to the side of a really hot vibration generator and having it
stop operating for any reason is considered "A Bad Thing". In the case
of rockets, it is considered "A Really Bad Thing". And the rockets will
take you out to where you can introduce your box to a bunch of gamma
rays - just to make life interesting for your EEPROMs, etc., and to keep
you appropriately humble. Due to the high reliability requirement, the
systems are dual redundant and each channel has to be able to take
immediate control if the other side is detected to have passed on to
meet its maker.

A real easy way to get in trouble and have to answer lots of
embarrassing questions and probably start looking for a new career in
the exciting world of the fast food industry is to have built completely
redundant systems except for one common link - a clock or interrupt line
for synchronization. If that chip or foil trace or wire should happen to
break, all your dual redundancy was for naught. Hence, we have to pull
some stunts to keep the two sides in synch.

Anyway - if you know of any texts or papers discussing techniques for
tightly synching two or more independent processors, please pass them
along. Thanks.

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669
***To reply, remove "bogon" from the domain name.***

    "Airplanes are interesting toys but of no military value."

        --  Marechal Ferdinand Foch, Professor of Strategy,
            Ecole Superieure de Guerre.




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-19  0:00 Processor Synchronization Marin David Condic
                   ` (2 preceding siblings ...)
  1999-01-21  0:00 ` Peter Jensen
@ 1999-01-21  0:00 ` The Bohemian Monk
  1999-01-21  0:00   ` Marin David Condic
  1999-01-22  0:00 ` Al Mok
  4 siblings, 1 reply; 14+ messages in thread
From: The Bohemian Monk @ 1999-01-21  0:00 UTC (permalink / raw)


After reading all the thread ... damn guys wake up.  A processor as 
simple as the 8088 has bus sync signals to allow multiple processors on 
a single buss, or a single memory.  Software does little for 
multiprocessing, hardware does the most, unless you program embedded in 
something like Forth.  With non-buss-master processesors you can use a 
PAL to envoke wait-states based on buss signals, all in hardware with 
simple memory table semaphores for access control.

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

Marin David Condic wrote:
> 
> I am preparing an in-house class on embedded system executives and I
> want to present a comprehensive overview of different designs. One of
> the areas I want to cover is processor synchronization. I am looking for
> a book or other reference material that discusses techniques for
> synchronizing independent processors. Specifically, I am interested in
> techniques used when building dual (or multiple) channel systems with
> relatively primitive communication between the two channels. (discrete
> lines, Manchester data link, etc.) Information pertaining to use of
> operating systems (e.g. Unix) and distributed systems may be interesting
> but not useful in this case.
> 
> The most general description of the problem domain I can come up with is
> this: The problem is at power-up, you have to get both processors
> ticking off at the same "heartbeat" so that they have the same frame of
> reference. Generally, you're going to have N cycles (frames, slots,
> whatever your favorite terminology is) and it is important that both
> processors be operating on cycle X at the same time. Once running, the
> processors have to detect drift in their cycling and correct for this so
> that they continue to both start on the same cycle at the same time. We
> have done this sort of thing in-house, but I'm looking for a discussion
> of a variety of algorithms and some analysis of the strengths &
> weaknesses of each.
> 
> If anybody has a favorite book, article or web-page on this subject, I
> would appreciate hearing about it. Thanks.
> 
> MDC
> --
> Marin David Condic
> Real Time & Embedded Systems, Propulsion Systems Analysis
> United Technologies, Pratt & Whitney, Large Military Engines
> M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
> Ph: 561.796.8997         Fx: 561.796.4669
> ***To reply, remove "bogon" from the domain name.***
> 
>     "Nobody shot me."
> 
>         --  Last words of Frank Gusenberg when asked by police who
>             shot him fourteen times with a machine gun in the Saint
>             Valentine's Day Massacre.

-- 
_________________________________________________________
 Christopher Passauer                 Logic Weavers
 Kerri Dean                           lgicwvrs@wctc.net
 715\421-4305




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-20  0:00   ` Marin David Condic
  1999-01-20  0:00     ` Ken Keys
@ 1999-01-21  0:00     ` Sune Falck
  1999-01-21  0:00       ` Marin David Condic
       [not found]     ` <36a83fe3.3666942@news.geccs.gecm.com>
  2 siblings, 1 reply; 14+ messages in thread
From: Sune Falck @ 1999-01-21  0:00 UTC (permalink / raw)


Just a pointer.

Digital transmisson systems for telephony have to stay in sync over long 
distances.

PCM systems such as SONET, SDH (Syncrounous Digital Hiearchy) and PDH
(Plesiosynconius Digital Hiarchy) are using methods for clock distribution
and syncronsiation that may be of interest. The time slots occur every 125
microsecond and they must stay in sync in the whole network.

/Sune Falck





^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-19  0:00 Processor Synchronization Marin David Condic
  1999-01-19  0:00 ` Ken Keys
  1999-01-20  0:00 ` dennison
@ 1999-01-21  0:00 ` Peter Jensen
  1999-01-21  0:00 ` The Bohemian Monk
  1999-01-22  0:00 ` Al Mok
  4 siblings, 0 replies; 14+ messages in thread
From: Peter Jensen @ 1999-01-21  0:00 UTC (permalink / raw)


I worked on a couple of double and triple redundant control systems.  The
first design used a processor synchronization scheme similar to the one you
described.  The "heart beat" was obtained from a 10 mb/s communications
port.  (Our goal was to sync within a few msec).  Critical data was
exchanged and compared via this port to determine any failures.  We had a
lot of trouble keeping the synchronization working from release to release
do to changes in the timing of the application software.

The second design abandoned synchronization all together and instead allowed
for a reasonable time delay when comparing critical data.  This was simpler,
but obviously can't be used for every type of redundant system.

There are a lot of other issues beyond the scope of this discussion that
must also be considered.

-Pete







^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-21  0:00   ` Marin David Condic
@ 1999-01-22  0:00     ` Tom Ziomek
  0 siblings, 0 replies; 14+ messages in thread
From: Tom Ziomek @ 1999-01-22  0:00 UTC (permalink / raw)


In article <36A741A2.E3DB7BCE@pwfl.com>,
Marin David Condic  <diespammer@pwfl.com> wrote:
>Our style of computer system for jet and rocket engines is not nearly
>that easy to do. The requirements won't allow for it. This box is
>strapped to the side of a really hot vibration generator and having it
>stop operating for any reason is considered "A Bad Thing". In the case
>of rockets, it is considered "A Really Bad Thing". And the rockets will
>take you out to where you can introduce your box to a bunch of gamma
>rays - just to make life interesting for your EEPROMs, etc., and to keep
>you appropriately humble. Due to the high reliability requirement, the
>systems are dual redundant and each channel has to be able to take
>immediate control if the other side is detected to have passed on to
>meet its maker.
>
>A real easy way to get in trouble and have to answer lots of
>embarrassing questions and probably start looking for a new career in
>the exciting world of the fast food industry is to have built completely
>redundant systems except for one common link - a clock or interrupt line
>for synchronization. If that chip or foil trace or wire should happen to
>break, all your dual redundancy was for naught. Hence, we have to pull
>some stunts to keep the two sides in synch.
>
>Anyway - if you know of any texts or papers discussing techniques for
>tightly synching two or more independent processors, please pass them
>along. Thanks.

This kind of stuff is certainly needed in some apps, and has been done be-
fore.  Not sure I know where--you could try looking at the Stratus computer
stuff (80s to mid-90s); they used sync'ed dual processors but I'm not sure
how tight that synchronizatio was.

There might be some stuff, or other refs, in the fault tolerant systems book
by Siewiorek (Prof. Daniel) and Schwarz.  I can get a ref for you if needed
but it should be pretty easy to look up based on what I recall here.

The best source I can think of is the annual proceedings from the IEEE FTCS
(Fault Tolerant Computing Symposium).  I went to a couple in the late '80s
and there were all sorts of papers that could help you.  A lot (but not all)
were more academic than reduced-to-practice, but a lot of those people did
actual lab implementations even if they didn't productize them.

Tom
-- 
Send email to user 'tomz' at domain 'comm.mot.com'.




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
  1999-01-19  0:00 Processor Synchronization Marin David Condic
                   ` (3 preceding siblings ...)
  1999-01-21  0:00 ` The Bohemian Monk
@ 1999-01-22  0:00 ` Al Mok
  4 siblings, 0 replies; 14+ messages in thread
From: Al Mok @ 1999-01-22  0:00 UTC (permalink / raw)


There is quite a bit on clock synchronization problems in the literature.
In my class, I teach Flaviu Cristian's probabilistic algorithm. A reference
is:

"Probabilistic clock synchronization" in DISTRIBUTED COMPUTING, 3:146-158,
1989.

-- Al Mok

BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT
BEAT THE CENSORBOT

In article <36A509DB.95F62C0B@pwfl.com>,
Marin David Condic  <diespammer@pwfl.com> wrote:
>I am preparing an in-house class on embedded system executives and I
>want to present a comprehensive overview of different designs. One of
>the areas I want to cover is processor synchronization. I am looking for
>a book or other reference material that discusses techniques for
>synchronizing independent processors. Specifically, I am interested in
>techniques used when building dual (or multiple) channel systems with
>relatively primitive communication between the two channels. (discrete
>lines, Manchester data link, etc.) Information pertaining to use of
>operating systems (e.g. Unix) and distributed systems may be interesting
>but not useful in this case.
>
>The most general description of the problem domain I can come up with is
>this: The problem is at power-up, you have to get both processors
>ticking off at the same "heartbeat" so that they have the same frame of
>reference. Generally, you're going to have N cycles (frames, slots,
>whatever your favorite terminology is) and it is important that both
>processors be operating on cycle X at the same time. Once running, the
>processors have to detect drift in their cycling and correct for this so
>that they continue to both start on the same cycle at the same time. We
>have done this sort of thing in-house, but I'm looking for a discussion
>of a variety of algorithms and some analysis of the strengths &
>weaknesses of each.
>
>If anybody has a favorite book, article or web-page on this subject, I
>would appreciate hearing about it. Thanks.
>
>MDC
>-- 
>Marin David Condic
>Real Time & Embedded Systems, Propulsion Systems Analysis
>United Technologies, Pratt & Whitney, Large Military Engines
>M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
>Ph: 561.796.8997         Fx: 561.796.4669
>***To reply, remove "bogon" from the domain name.***
>
>    "Nobody shot me."
>
>        --  Last words of Frank Gusenberg when asked by police who
>            shot him fourteen times with a machine gun in the Saint
>            Valentine's Day Massacre.


-- 
Aloysius K. Mok      mok@cs.utexas.edu      Department of Computer Science
                                            University of Texas at Austin
"Why?" "Why not?"                           Austin, Texas 78712
                                            (512)471-9542




^ permalink raw reply	[flat|nested] 14+ messages in thread

* Re: Processor Synchronization
       [not found]     ` <36a83fe3.3666942@news.geccs.gecm.com>
@ 1999-01-22  0:00       ` Marin David Condic
  0 siblings, 0 replies; 14+ messages in thread
From: Marin David Condic @ 1999-01-22  0:00 UTC (permalink / raw)
  To: Brian Orpin

Brian Orpin wrote:
> 
> OK maybe I am being thick here but isn't the discrete a single point of
> failure?  If that goes which processor takes over and how does it know it
> should and that it isn't just the link that has gone down?  If both
> processors check for instability and take over if it is detected do they
> need to be closely synchronised?

Of course it is impossible to describe the entirety of our architecture
in a newsgroup post, so expect some inaccuracy. Also, I am describing an
"in general" architecture that is used by our controls. The control for
the F119 engine (Advanced Tactical Fighter) actually has three
processors per channel and two channels. (much more complex sync
problem!)  The Joint Strike Fighter is yet again even more complex. So
it is hard to give you a schematic here in a post which can't be picked
apart.

Yes, the discrete between both channels would be a single point failure,
but not one that necessarily causes the control to fail
catastrophically. If the discrete goes down (assuming you have no other
means of communicating between the two channels, which we do - a
manchester data link.) you can at least reason about what to do next: I
know I'm alive. The other guy may be dead or alive. If he's dead and I
take control, that's cool. If he's alive and I take control, is that
bad? Are the actuators dual active? Are there any ways of determining if
the other side is still controlling the actuators?, etc... In any event,
you're not necessarily putting a pilot in the drink or blowing up a
billion dollar space payload because a wire broke loose between the two
channels.

I hope that sheds a little light on it. It really becomes a fascinating
problem when you get into the FDA aspects of the control and the system
it runs!

MDC
-- 
Marin David Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669
***To reply, remove "bogon" from the domain name.***

    "Airplanes are interesting toys but of no military value."

        --  Marechal Ferdinand Foch, Professor of Strategy,
            Ecole Superieure de Guerre.




^ permalink raw reply	[flat|nested] 14+ messages in thread

end of thread, other threads:[~1999-01-22  0:00 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1999-01-19  0:00 Processor Synchronization Marin David Condic
1999-01-19  0:00 ` Ken Keys
1999-01-20  0:00   ` Marin David Condic
1999-01-20  0:00     ` Ken Keys
1999-01-21  0:00       ` Marin David Condic
1999-01-21  0:00     ` Sune Falck
1999-01-21  0:00       ` Marin David Condic
     [not found]     ` <36a83fe3.3666942@news.geccs.gecm.com>
1999-01-22  0:00       ` Marin David Condic
1999-01-20  0:00 ` dennison
1999-01-21  0:00 ` Peter Jensen
1999-01-21  0:00 ` The Bohemian Monk
1999-01-21  0:00   ` Marin David Condic
1999-01-22  0:00     ` Tom Ziomek
1999-01-22  0:00 ` Al Mok

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox