Difference between revisions of "Flameman/m68ec0x0IDP"

From eLinux.org
Jump to: navigation, search
(proof)
(Added to category 68k)
(20 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
For more interesting projects done by Flameman, be sure to checkout his [[Flameman#master_index|project index]]
 +
 
EARLY PROOF VERSION OF THIS PAGE  
 
EARLY PROOF VERSION OF THIS PAGE  
  
Line 13: Line 15:
  
 
== m68k OS ==
 
== m68k OS ==
 +
 +
=== 68000 Tiny Basic ===
 +
 +
The 100th issue of Dr. Dobb's Journal (February 1985) published an article Gordon Brandly wrote describing a Tiny Basic interpreter he had written for the Motorola 68000 microprocessor.
 +
 +
* 68000 Tiny Basic version 1.2 for Quelo CP/M 68000 cross-assembler (provided in the article)
 +
* 68000 Tiny Basic version 1.2 for gnu as (under porting)
  
 
=== 1985: Terra Nova Communications: OS design ===
 
=== 1985: Terra Nova Communications: OS design ===
Line 205: Line 214:
  
 
=== 1987: "BYTE magazine September 1987, unix system design with m68k" ===
 
=== 1987: "BYTE magazine September 1987, unix system design with m68k" ===
 +
 +
=== virtualization requirements with Motorola MC68000 ===
 +
 +
The '''Popek and Goldberg virtualization requirements''' are a set of sufficient conditions for a computer architecture to efficiently support system Full virtualization. They were introduced by Gerald J. Popek and Robert P. Goldberg in their 1974 article "Formal Requirements for Virtualizable Third Generation Architectures". Even though the requirements are derived under simplifying assumptions, they still represent a convenient way of determining whether a computer architecture supports efficient virtualization and provide guidelines for the design of virtualized computer architectures.
 +
 +
System  are virtual machines capable of virtualizing a full set of hardware resources, including a processor (or processors), memory and storage resources and peripheral devices.
 +
A virtual machine monitor (VMM) is the piece of software that provides the abstraction of a virtual machine. There are three properties of interest when analyzing the environment created by a VMM:
 +
; Equivalence : A program running under the VMM should exhibit a behavior essentially identical to that demonstrated when running on an equivalent machine directly.
 +
; Resource control : The VMM must be in complete control of the virtualized resources.
 +
; Efficiency : A statistically dominant fraction of machine instructions must be executed without VMM intervention.
 +
In Popek and Goldberg terminology, a VMM must present all three properties. In today's terminology, VMM are typically assumed to satisfy the equivalence and resource control properties. So, in a sense, Popek and Goldberg's VMMs are today's efficient VMM.
 +
 +
Popek and Goldberg describe the characteristics that the Instruction Set Architecture (ISA) of the physical machine must possess in order to run VMMs which possess the above properties.
 +
Their analysis derives such characteristics using a model of "third generation architectures" (e.g., IBM 360, Honeywell 6000, DEC PDP-10) that is nevertheless general enough to be extended to modern machines. This model includes a processor that operates in either system or user mode, and has access to linear, uniformly addressable memory. It is assumed that a subset of the instruction set is available only when in system mode and that memory is addressed relative to a relocation register. I/O and interrupts are not modelled.
 +
 +
==== Virtualization requirements ====
 +
 +
To derive their virtualization requirements, Popek and Goldberg introduce a classification of instructions of an ISA into 3 different groups:
 +
; Privileged instructions : Those that Trap (computing) if the processor is in user mode and do not trap if it is in system mode.
 +
; Control sensitive instructions : Those that attempt to change the configuration of resources in the system.
 +
; Behavior sensitive instructions : Those whose behavior or result depends on the configuration of resources (the content of the relocation register or the processor's mode).
 +
 +
The main result of Popek and Goldberg's analysis can then be expressed as follows.
 +
 +
'''Theorem 1'''. For any conventional third-generation computer, a VMM may be constructed if the set of sensitive instructions for that computer is a subset of the set of privileged instructions.
 +
 +
Intuitively, the theorem states that to build a VMM it is sufficient that all instructions that could affect the correct functioning of the VMM (sensitive instructions) always trap and pass control to the VMM. This guarantees the resource control property. Non-privileged instructions must instead be executed natively (i.e., efficiently). The holding of the equivalence property also follows.
 +
 +
A related problem is that of deriving the ISA requirements for recursive virtualization, that is, the conditions under which a VMM that can run on a copy of itself can be built. Popek and Goldberg present the following (sufficient) conditions.
 +
 +
'''Theorem 2'''. A conventional third-generation computer is recursively virtualizable if
 +
# it is virtualizable and
 +
# a VMM without any timing dependencies can be constructed for it.
 +
 +
==== Handling critical instructions ====
 +
 +
The conditions for ISA virtualization expressed in Theorem 1 may be relaxed at the expense of the efficiency property.  VMMs for non-virtualizable ISAs (in the Popek and Goldberg's sense) have routinely been built.
 +
 +
The virtualization of such architectures requires correct handling of ''critical instructions'', i.e., sensitive but unprivileged instructions. One approach, known as ''patching'', adopts techniques commonly used in dynamic recompilation: critical instructions are discovered at run-time and replaced with a trap into the VMM. Various mechanisms, such as the caching of emulation code or hardware assists, have been proposed to make the patching process more efficient. A different approach is that of paravirtualization, which requires guest operating systems to be modified (''ported'') before running in the virtual environment.
 +
 +
==== Instruction sets ====
 +
 +
This section presents some relevant architectures and how they relate to the virtualization requirements.
 +
 +
==== Motorola MC68000 ====
 +
 +
The Motorola MC68000 has a single unprivileged sensitive instruction:
 +
* MOVE from SR
 +
 +
This instruction is sensitive because it allows access to the entire status register, which includes not only the Status register condition codes but also the user/supervisor bit, interrupt level, and trace control.  In most later family members, starting with the Motorola 68010, the MOVE from SR instruction was made privileged, and a new MOVE from CCR instruction was provided to allow access to the condition code register only.
 +
 +
== Handling critical instructions ==
 +
 +
The conditions for ISA virtualization expressed in Theorem 1 may be relaxed at the expense of the efficiency property.  VMMs for non-virtualizable ISAs (in the Popek and Goldberg's sense) have routinely been built.
 +
 +
The virtualization of such architectures requires correct handling of ''critical instructions'', i.e., sensitive but unprivileged instructions. One approach, known as ''patching'', adopts techniques commonly used in dynamic recompilation: critical instructions are discovered at run-time and replaced with a trap into the VMM. Various mechanisms, such as the caching of emulation code or hardware assists, have been proposed to make the patching process more efficient. A different approach is that of paravirtualization, which requires guest operating systems to be modified (''ported'') before running in the virtual environment.
 +
 +
==== Instruction sets ====
 +
 +
This section presents some relevant architectures and how they relate to the virtualization requirements.
 +
 +
 +
==== Motorola MC68000 ====
 +
 +
The Motorola MC68000 has a single unprivileged sensitive instruction:
 +
* MOVE from SR
 +
 +
This instruction is sensitive because it allows access to the entire status register, which includes not only the Status register condition codes but also the user/supervisor bit, interrupt level, and trace control.  In most later family members, starting with the MC68010, the MOVE from SR instruction was made privileged, and a new MOVE from CCR instruction was provided to allow access to the condition code register only.
  
 
== the m68ec0x0idp board ==
 
== the m68ec0x0idp board ==
Line 493: Line 570:
  
 
</pre>
 
</pre>
 +
 +
 +
 +
= the m68k =
 +
 +
== ebook ==
 +
 +
http://www.toodoc.com/mc68008-ebook.html
 +
 +
 +
== mc68020 brief ==
 +
 +
Motorola 68020 (MC68020) is a 32-bit microprocessor compatible with earlier members of 680x0 family - 68000, 68008 and 68010. Address bus width on the 68020 is increased to 32 bits, which allows the processor to address up to 4 GB of memory. Data bus width is also increased to 32 bits, though if necessary the 68020 can work with 8- and 16-bit data buses. Other Motorola 68020 enhancements include:
 +
 +
* Execution time of many instructions was reduced.
 +
* To improve CPU performance, a 256-byte instruction cache was added to the CPU.
 +
* The CPU includes new control registers.
 +
* The CPU has new addressing modes: memory indirect addressing modes, scaled index, and larger displacements.
 +
* New instructions were added to 68020 instruction set: bit field instructions, compare instructions, call module and pack/unpack BCD.
 +
* The MC68020 provides hardware support for Motorola 68881 and 68882 Floating-Point Units.
 +
* Accessing mis-aligned word or long-word data no longer results in a system error, though access to misaligned data is not as fast as access to properly aligned data.
 +
 +
Motorola also manufactured MC68EC020 - embedded version of the MC68020 CPU. The 68EC020 had only 24-bit address bus, and could address up to 16 MB of physical memory. The MC68EC020 was housed in different packages than the Motorola 68020 microprocessor.
 +
 +
 +
model:
 +
clock.min:
 +
clock.max:
 +
 +
== MC68000/008/010 FAQ ==
 +
 +
 +
 +
=== Is it okay to tie the HALT* and RESET* lines together on the MC68000 together? ===
 +
 +
 +
Tying HALT* and RESET* together will not cause any problems for the MC68000.As you probably know, RESET* on the MC68000 should never be asserted without asserting HALT* as well. You must realize, however, that tying the two lines together introduces the following three restrictions:
 +
 +
* 1 You can not do hardware single-stepping of the processor.
 +
* 2 You can not perform a retry.
 +
* 3 The processor will reset itself if you get a double bus error (by asserting HALT*).
 +
 +
Many systems can function within the bounds of the above restrictions and operate without problems when HALT* and RESET* are tied together.
 +
 +
=== Should I assert RESET* on the MC68000 without asserting HALT* as well? ===
 +
 +
 +
On the MC68000/MC68EC000/MC68008 processors, RESET* should never be
 +
asserted without asserting HALT* as well. You may bring about the assertion
 +
of HALT* with RESET* through external logic or by tying the two lines
 +
together. You must realize, however, that tying the two lines together
 +
introduces the following three restrictions:
 +
* 1 You can not do hardware single-stepping of the processor.
 +
* 2 You cannot perform a retry.
 +
* 3 The processor will reset itself if you get a double bus error (by asserting  HALT*).
 +
 +
=== Is it okay to assert the MC68000 VPA* and DTACK* inputs at the same time? ===
 +
 +
 +
DTACK* should never be asserted while VPA* is asserted. Asserting DTACK*
 +
and VPA* at the same time will produce unpredictable results.
 +
 +
 +
 +
=== Will the MC68000 support 4 megabytes of DRAM using 1x9 1-Mbyte SIMMs? ===
 +
 +
 +
You should have no problems interfacing standard DRAM SIMMs to the
 +
MC68000.Note that the MC68000 does not burst so you do not need any special
 +
type of DRAM such as page-mode DRAM which would normally be required to
 +
support bursting.
 +
 +
 +
 +
=== What kind of cache design would you recommend for the MC68000? ===
 +
 +
 +
A system can be designed around an MC68000 which uses relatively cheap (80
 +
ns or 100 ns) DRAM and yet provides zero wait-state accesses. Therefore, we
 +
do not recommend using a cache with the MC68000.
 +
 +
 +
 +
=== How do you perform a long-word write with an MC68000 with a 16-bit bus? ===
 +
 +
 +
The MC68000 instruction set supports long-word moves. When the processor
 +
executes an instruction that calls for a long-word write, it will perform
 +
two 16-bit writes. Note that bus arbitration is done on a cycle-by-cycle
 +
basis, so the bus can be arbitrated away from the MC68000 after the first
 +
of the two 16-bit writes, and the processor will complete the long-word
 +
write after it retakes the bus.
 +
 +
 +
 +
=== What is the difference between an MC68000 and an MC68008? ===
 +
 +
 +
* 1 The MC68000 is a 16-bit processor, whereas the MC68008 is an 8-bit processor.
 +
* 2 Therefore, UDS* and LDS* on the MC68000 are replaced by DS* and A0 on the MC68008.
 +
* 3 The MC68008 uses two-wire bus arbitration, whereas the MC68000 uses three-wire bus arbitration.
 +
* 4 The MC68000 supports three interrupt lines and, therefore, seven interrupt levels. The MC68008 supports only two interrupt lines and, therefore, three interrupt levels. The MC68008 PLCC package supports three interrupt lines like the MC68000.
 +
* 5 The MC68000 provides 16 Mbytes of addressable space. The MC68008 has 20 address lines creating 1 Mbyte of addressable space. The MC68008 PLCC package has 21 address lines for 2 Mbytes of addressable space.
 +
* 6 The MC68008 does not have a VMA* signal as does the MC68000, but this signal can be generated with some simple external logic (see M68000 Users Manual (M68000UM/AD)).
 +
* 7 The MC68000 and MC68008 are not pin compatible.
 +
 +
It should be noted that the MC68EC000 provides a lower cost solution compared to the MC68008 and is available at more frequencies than the MC68008. The MC68EC000 can operate in either 8-bit or 16-bit mode and does not include the 6800 peripheral interface, but is virtually identical to the MC68000 in every other way. If you are planning to do a design with the MC68008, it would be worth your time to consider the option of using the MC68EC000 instead.
 +
 +
=== During a byte access on the MC68000, which bits of the data bus are read/written? ===
 +
 +
 +
If the MC68000 asserts UDS*, then bits 15-8 of the data bus will be used.
 +
If the MC68000 asserts LDS*, then bits 7-0 of the data bus will be used.
 +
 +
=== The MC68230 is an 8-bit peripheral. On which byte lane of the MC68000 should I place the MC68230? ===
 +
 +
 +
The MC68230 should be placed on the lower byte lane (i.e., on data bits 7-
 +
0) of the MC68000. This is required because when the MC68230 provides an
 +
interrupt vector for the MC68000 it must be right-aligned. In all other
 +
respects, the two byte lanes of the MC68000 would be equally qualified for
 +
attaching the MC68230. Note that your software must be written so that all
 +
accesses to the MC68230 are byte accesses to even addresses to make sure
 +
the proper byte lane (bits 7-0) of the MC68000 are used.
 +
 +
 +
 +
=== What is the state of AS* during reset on the MC68000 and how long after reset before AS* becomes valid? ===
 +
 +
 +
AS* remains inactive during reset. It will take an undetermined amount of time after reset before AS* will become valid. However, if you are not getting an AS* after you come out of reset, you should check the following signals:
 +
 +
* 1 Check to make sure BR* and BGACK* are negated to make sure you are not arbitrating the bus away from the MC68000.
 +
* 2 Check to make sure HALT* is negated.
 +
 +
=== Intel has a pin that allows the signals to tri-state. Does the MC68000 have something similar? ===
 +
 +
 +
Motorola does not provide such a pin. However, if you want to cause the
 +
signals from the MC68000 to tri-state, you can arbitrate the bus away from
 +
the MC68000 which will cause it to tri-state all signals with the exception
 +
of the bus arbitration signals.
 +
 +
 +
 +
=== In an MC68000 system, we desire that all registers of an 8-bit peripheral be mapped on byte boundaries. How can we do this? ===
 +
 +
 +
Essentially, what is needed is pseudo-"dynamic bus sizing." This feature is
 +
implemented on the MC68020 and MC68030, but not on the MC68000. There is no
 +
glueless way of implementing dynamic bus sizing on the MC68000. The
 +
cheapest solution is to place the peripheral on one of the byte lanes and
 +
use the MOVEP instruction. The UDS/LDS signals will uniquely determine the
 +
byte of the data bus.
 +
 +
 +
 +
=== What is the interrupt latency for the MC68000 family? ===
 +
 +
 +
Interrupt latency is the time from when an interrupt occurs to when the first instruction of the interrupt handler is started. The amount of time required for this will depend the processor, what the processor is doing when the interrupt occurs, and the speed with which the memory responds to
 +
reads and writes.
 +
 +
Worst case interrupt latency is the absolute maximum amount of time it will take for the processor to respond to the interrupt for a given set of conditions. A given interrupt may respond sooner (and usually will), but it will never take longer. The selection of the conditions can have a major impact on the interrupt latency. For example, the number of wait states on writes will effect the time it takes to stack the interrupt stack frame. An infinite number of wait states on writes would result in an infinite interrupt latency.
 +
 +
The following lists the interrupt latency for a given processor and the conditions assumed.
 +
 +
<pre>
 +
MPU          Conditions                                    Latency
 +
MC68EC000    MOVEM.L xxx.L,D0-D7/A0-A7
 +
16-bit        DIVS xxx.L, Dn
 +
data bus      interrupt at beginning of MOVEM                378
 +
clks
 +
 +
MC68EC000    MOVEM.L xxx.L,D0-D7/A0-A7
 +
8-bit        DIVS xxx.L, Dn
 +
data bus      interrupt at beginning of MOVEM                574
 +
clks
 +
 +
MC68EC020    MOVEM.L <memory indirect ea>,D0-D7/A0-A7
 +
MC68EC030    interrupt at the beginning of MOVEM            197
 +
clks
 +
32-bit bus    no bus errors
 +
 +
MC68EC040    any integer instruction stream,
 +
              no back-to back 64-bit divide instructions
 +
              no CAS,TAS,CAS2 instructions                    78
 +
clks
 +
</pre>
 +
 +
=== How many transistors are on each of the MC68000 family devices? ===
 +
 +
 +
<pre>
 +
DEVICE          TRANSISTORS
 +
 +
MC68000          68,000
 +
MC68EC000        68,000
 +
MC68HC000        68,000
 +
MC68HC001        68,000
 +
MC68008          70,000
 +
MC68010          84,000
 +
MC68020          190,000
 +
MC68EC020        190,000
 +
MC68030          273,000
 +
MC68EC030        251,000
 +
MC68040        1,170,000
 +
MC68EC040        962,000
 +
MC68LC040        813,500
 +
MC68230          16,700
 +
MC68302          320,000
 +
MC68330          235,000
 +
MC68340          350,000
 +
MC68440          26,000
 +
MC68450          40,000
 +
MC68451          34,000
 +
MC68661            6,000
 +
MC68681            9,743
 +
MC68851          210,000
 +
MC68881          155,000
 +
MC68882          176,000
 +
MC68901            9,100
 +
</pre>
 +
 +
 +
=== If BR* is asserted before RESET* negates, when will the MC68HC000 take control of the bus? ===
 +
 +
 +
If BR* is asserted when the MC68HC000 comes out of reset, it will assert BG* in order to grant the bus to the requesting device. The requesting device will then most likely respond with BGACK*. The MC68HC000 will not take back the bus until BR* and BGACK* are both negated.
 +
 +
[[Category:68k]]

Revision as of 13:37, 12 April 2011

For more interesting projects done by Flameman, be sure to checkout his project index

EARLY PROOF VERSION OF THIS PAGE

Contents

m68ec0x0idp, dream, history, project

http://www.netbsd.org/docs/Hardware/Chips/Motorola/

I bought "BYTE magazine September 1987"; there is a sweet article about 68k & unix.

Byte68k.jpg

Today MOTOROLA semiconductor group is sold to Freescale. The so called "company evolution" .... Happened at the end of 2004. When Motorola was running the semiconductors desk, i was provided this IDP board as "68k learner". Since 1999 i have been looking around for the board that i'd like to develop in my lowest priority free time. She eats 2.5A, so at 5V that means 13Watt .... this because she has a lot of fun and troubles


m68k OS

68000 Tiny Basic

The 100th issue of Dr. Dobb's Journal (February 1985) published an article Gordon Brandly wrote describing a Tiny Basic interpreter he had written for the Motorola 68000 microprocessor.

  • 68000 Tiny Basic version 1.2 for Quelo CP/M 68000 cross-assembler (provided in the article)
  • 68000 Tiny Basic version 1.2 for gnu as (under porting)

1985: Terra Nova Communications: OS design

Created real-time multiuser OS for dialup conferencing. Kernel source published in Dr. Dobb's Journal (1/86). Innovative interface inspired hundreds of similar systems. One of the first tree-structured BBS systems. 68K asm, multitasking kernel, custom memory manager, custom disk I/O manager, custom serial drivers.

;
;       Terra Nova Communications multi-tasking kernel
;       Initialization and task-switcher
;
;       Note: this is not intended to be a complete listing.  It's only
;       a sample of some of the techniques used in our system.
;

                PSECT   Kernel
       
;              External symbols (defined in other code segments)
                EXTERN  VecTable, ;vector table for hardware vector list
                        JMPTable,       ;jump table for system calls
                        JMPTabLen,      ;length of jump table in longwords
                        KernEnd,        ;end of kernel code item in heap
                        IOInit,  ;our private I/O initialization routine
                        HeapInit,       ;our private heap initialization
                        SysInit,        ;system variable initializer
                        SysConMon,      ;entry point for system console
                                        ;monitor task
                        HeapMunger,     ;entry point for heap munger task
                        DiskMunger      ;entry point for disk munger task

;              Entry points in this module (referenced from elsewhere)
                ENTRY   Start,    ;primary entry point to boot our OS
                        ConSwitch,      ;main context switcher
                        ConSwSleep      ;alternate context switcher (puts
                                        ;calling task to sleep)

;              Include files (mostly equates)
                INCLUDE SysEqu      ;contains the low-memory absolute
                                        ;address equates (jump table, etc)
                INCLUDE HeapDef    ;defines the heap data structure
                INCLUDE SysIO        ;contains hardware I/O equates

;              Miscellaneous storage
CodeHeap        DS.L    8      ;heap header for kernel heap item
StackEnd        DS.L    40    ;system stack before tasking starts
StackBegin      DS.L  0  ;top of startup stack area

;              Pre-tasking initialization
;              this code works in single-task mode
;              prior to the invocation of the context switcher
Start         ;Initial entry.  Calling operating system is still
                      ;alive and kicking at this point.
TakeOver        LEA     ReEntry,A1   ;point to re-entry instruction
                MOVE.L  A1,$20.W  ;move short absolute to the vector
                                        ;for privilege exceptions
                MOVE    USP,A0            ;try a privileged instruction.  If it
                        ;works, then we're in priv. mode. If not, then trap to
                      ;ReEntry and be in privileged mode anyway
ReEntry  LEA      StackBegin,A7 ;set up initial stack

;              Turn off all interrupts in the system
;              Note: this is device-specific code.
;              The labels in the operand fields are from our own
;              SysIO include file.
                CLR.B   FDCIntMask ;clear floppy disk & system console
                CLR.B   HDIntMask  ;clear hard disk completion int. mask
                CLR.B   SerIO1IntMask      ;clear serial boards
                CLR.B   SerIO2IntMask

;              Initialize the vector table
;              Copy the vectors from an assembled table (in another module)
;              into the actual hardware vector list in low RAM
                LEA     VecTable,A0  ;source (in another code segment)
                LEA     $0.W,A1            ;destination (begins at $00 0000)
                MOVE    #191,D7          ;192 longwords to move
VecMove  MOVE.L   (A0)+,(A1)+        ;move a longword
                DBRA    D7,VecMove  ;repeat till done (fast loop on 68010)

;              Copy system routine JMP table from assembled object code (in
;              another module) to low memory jump table, where everyone
;              can get at them.
                LEA     JMPTable,A0  ;source
                LEA     System.W,A1  ;dest. (name of first system call in
                        ;the jump table.  "System" is from the SysEqu include
                      ;file.  It's the context switcher)
                MOVE    #JMPTabLen/4,D7     ;number of longwords to move
JPTMove  MOVE.L   (A0)+,(A1)+        ;move a longword
                DBRA    D7,JPTMove  ;repeat till done (fast loop on 68010)

;              Clear low memory to zero (between jmp table and kernel)
                LEA     StackEnd,A1  ;point to top of destination
                        ;and bottom of destination (end of the jump table)
                LEA     System+JMPTabLen.W,A0
                SUBA    A0,A1              ;calculate the length
                MOVE.L  A1,D7          ;move to D7 for counting
                LSR.L   #4,D7           ;divide by 16 for 16-byte blocks
LowClr    CLR.L     (A0)+                ;clear 16 bytes, quickly
                CLR.L   (A0)+
                CLR.L   (A0)+
                CLR.L   (A0)+
                DBRA    D7,LowClr   ;do it until done.

;              Clear high memory to zero (between kernel and end of RAM)
;              (RAMEnd is first byte beyond RAM, defined in SysEqu)
                LEA     RAMEnd,A1    ;point to top of destination
                        ;and bottom of destination (end of the jump table)
                LEA     KernEnd,A0
                SUBA    A0,A1              ;calc the length
                MOVE.L  A1,D7          ;move to D7 for counting
                LSR.L   #4,D7           ;divide by 16 for 16-byte blocks
HiClr      CLR.L      (A0)+  ;clear 16 bytes, quickly
                CLR.L   (A0)+
                CLR.L   (A0)+
                CLR.L   (A0)+
                DBRA    D7,HiClr    ;do it until done.

;              Initialize all of the primary I/O devices
;              Note: this is a device specific routine not treated in the article.
                JSR     IOInit
       
;              Initialize the heap
;              Note: this is a routine in the heap manager, which creates
;              valid heap headers for the three initial heap items discussed
;              in the text: the deletion below the kernel, the kernel code
;              item, and the deletion above the kernel.
                JSR     HeapInit

;              Initialize the system zone of low memory
;              Note: this sets up the TCB and master handle arrays, as
;              discussed in the text, as well as initializing the time of day
;              and the date and the other miscellaneous system values.
                JSR     SysInit

;              Spawn off the initial tasks
;              This will create TCBs and TData items for the tasks, but won't
;              invoke them.  They're invoked only by the context switcher.
                LEA     SysConMon,A0 ;point to system console entry point
                MOVE.L  #4096,D0  ;tell it how much RAM for TData
                JSR     Spawn                ;jump through jump table entry
                        ;("Spawn" is a jump table equate in SysEqu)
                LEA     HeapMunger,A0        ;spawn the heap munger
                MOVE.L  #512,D0      ;heap munger's TData size
                JSR     Spawn
                LEA     DiskMunger,A0        ;Spawn the disk munger
                MOVE.L  #8192,D0  ;(TData includes one disk buffer)
                JSR     Spawn

                LEA     TCB1.W,A2    ;get address of first TCB in array
                                        ;(TCB1 is defined in SysEqu)
                BRA.S   ConSw1          ;now start the context switcher!

;              Context Switcher: primary version
;              Simple task-switch, nothing fancy.
;              SysFlags is a low-RAM system flag byte, defined in SysEqu.
;              The data structure for the TData item is defined in SysEqu.
;              The data structure for the TCB is defined in SysEqu.
ConSwitch       BTST   #StopSys,SysFlags.W ;task switching inhibited?
                BNE.S   ConSwX          ;yes, exit back to caller
                MOVE.L  OurTCB(A5),A0     ;get TCB address from TData
                SUBA.L  A5,SP          ;subtract TData base addr from stack
                MOVE.L  SP,TCBSP(A0)      ;save relative displacement in TCB

                MOVE.L  TCBNxt(A0),A2     ;get address of next TCB
ConSw1    MOVE.L    TCBA5(A2),A5        ;get new TData base address
                MOVE.L  TCBSP(A2),SP      ;get stack relative displacement
                ADDA.L  A5,SP          ;restore absolute address
ConSwX    RTS                     ;return to next task

;              Context Switcher: alternate version
;              Put the calling task to sleep.
ConSwSleep      BTST  #StopSys,SysFlags.W ;task switching inhibited?
                BNE.S   ConSwX          ;yes, exit back to caller
                                        ;without going to sleep
                MOVE.L  OurTCB(A5),A0     ;get TCB address from TData
                SUBA.L  A5,SP          ;subtract TData base addr from stack
                MOVE.L  SP,TCBSP(A0)      ;save relative displacement in TCB

                MOVE.L  TCBNxt(A0),A2     ;get address of next TCB
                MOVE.L  TCBPrev(A0),A1    ;get addr of previous TCB
                MOVE.L  A2,TCBNxt(A1)     ;close the pointers around the now-
                MOVE.L  A1,TCBPrev(A2)    ;sleeping task.
                MOVE.B  #Sleep,TCBState(A0) ;mark it as asleep

                MOVE.L  TCBA5(A2),A5      ;get new TData base address
                MOVE.L  TCBSP(A2),SP      ;get stack relative displacement
                ADDA.L  A5,SP          ;restore absolute address
                RTS               ;return to next task 


1985: Steve Passe Kernel for the MC68000

1987: "BYTE magazine September 1987, unix system design with m68k"

virtualization requirements with Motorola MC68000

The Popek and Goldberg virtualization requirements are a set of sufficient conditions for a computer architecture to efficiently support system Full virtualization. They were introduced by Gerald J. Popek and Robert P. Goldberg in their 1974 article "Formal Requirements for Virtualizable Third Generation Architectures". Even though the requirements are derived under simplifying assumptions, they still represent a convenient way of determining whether a computer architecture supports efficient virtualization and provide guidelines for the design of virtualized computer architectures.

System are virtual machines capable of virtualizing a full set of hardware resources, including a processor (or processors), memory and storage resources and peripheral devices. A virtual machine monitor (VMM) is the piece of software that provides the abstraction of a virtual machine. There are three properties of interest when analyzing the environment created by a VMM:

Equivalence 
A program running under the VMM should exhibit a behavior essentially identical to that demonstrated when running on an equivalent machine directly.
Resource control 
The VMM must be in complete control of the virtualized resources.
Efficiency 
A statistically dominant fraction of machine instructions must be executed without VMM intervention.

In Popek and Goldberg terminology, a VMM must present all three properties. In today's terminology, VMM are typically assumed to satisfy the equivalence and resource control properties. So, in a sense, Popek and Goldberg's VMMs are today's efficient VMM.

Popek and Goldberg describe the characteristics that the Instruction Set Architecture (ISA) of the physical machine must possess in order to run VMMs which possess the above properties. Their analysis derives such characteristics using a model of "third generation architectures" (e.g., IBM 360, Honeywell 6000, DEC PDP-10) that is nevertheless general enough to be extended to modern machines. This model includes a processor that operates in either system or user mode, and has access to linear, uniformly addressable memory. It is assumed that a subset of the instruction set is available only when in system mode and that memory is addressed relative to a relocation register. I/O and interrupts are not modelled.

Virtualization requirements

To derive their virtualization requirements, Popek and Goldberg introduce a classification of instructions of an ISA into 3 different groups:

Privileged instructions 
Those that Trap (computing) if the processor is in user mode and do not trap if it is in system mode.
Control sensitive instructions 
Those that attempt to change the configuration of resources in the system.
Behavior sensitive instructions 
Those whose behavior or result depends on the configuration of resources (the content of the relocation register or the processor's mode).

The main result of Popek and Goldberg's analysis can then be expressed as follows.

Theorem 1. For any conventional third-generation computer, a VMM may be constructed if the set of sensitive instructions for that computer is a subset of the set of privileged instructions.

Intuitively, the theorem states that to build a VMM it is sufficient that all instructions that could affect the correct functioning of the VMM (sensitive instructions) always trap and pass control to the VMM. This guarantees the resource control property. Non-privileged instructions must instead be executed natively (i.e., efficiently). The holding of the equivalence property also follows.

A related problem is that of deriving the ISA requirements for recursive virtualization, that is, the conditions under which a VMM that can run on a copy of itself can be built. Popek and Goldberg present the following (sufficient) conditions.

Theorem 2. A conventional third-generation computer is recursively virtualizable if

  1. it is virtualizable and
  2. a VMM without any timing dependencies can be constructed for it.

Handling critical instructions

The conditions for ISA virtualization expressed in Theorem 1 may be relaxed at the expense of the efficiency property. VMMs for non-virtualizable ISAs (in the Popek and Goldberg's sense) have routinely been built.

The virtualization of such architectures requires correct handling of critical instructions, i.e., sensitive but unprivileged instructions. One approach, known as patching, adopts techniques commonly used in dynamic recompilation: critical instructions are discovered at run-time and replaced with a trap into the VMM. Various mechanisms, such as the caching of emulation code or hardware assists, have been proposed to make the patching process more efficient. A different approach is that of paravirtualization, which requires guest operating systems to be modified (ported) before running in the virtual environment.

Instruction sets

This section presents some relevant architectures and how they relate to the virtualization requirements.

Motorola MC68000

The Motorola MC68000 has a single unprivileged sensitive instruction:

  • MOVE from SR

This instruction is sensitive because it allows access to the entire status register, which includes not only the Status register condition codes but also the user/supervisor bit, interrupt level, and trace control. In most later family members, starting with the Motorola 68010, the MOVE from SR instruction was made privileged, and a new MOVE from CCR instruction was provided to allow access to the condition code register only.

Handling critical instructions

The conditions for ISA virtualization expressed in Theorem 1 may be relaxed at the expense of the efficiency property. VMMs for non-virtualizable ISAs (in the Popek and Goldberg's sense) have routinely been built.

The virtualization of such architectures requires correct handling of critical instructions, i.e., sensitive but unprivileged instructions. One approach, known as patching, adopts techniques commonly used in dynamic recompilation: critical instructions are discovered at run-time and replaced with a trap into the VMM. Various mechanisms, such as the caching of emulation code or hardware assists, have been proposed to make the patching process more efficient. A different approach is that of paravirtualization, which requires guest operating systems to be modified (ported) before running in the virtual environment.

Instruction sets

This section presents some relevant architectures and how they relate to the virtualization requirements.


Motorola MC68000

The Motorola MC68000 has a single unprivileged sensitive instruction:

  • MOVE from SR

This instruction is sensitive because it allows access to the entire status register, which includes not only the Status register condition codes but also the user/supervisor bit, interrupt level, and trace control. In most later family members, starting with the MC68010, the MOVE from SR instruction was made privileged, and a new MOVE from CCR instruction was provided to allow access to the condition code register only.

the m68ec0x0idp board

About the motorola board the motorola board is "IDP68EC0x0" part number

M68ec0xIDP-idea.jpg

On the board there are the following devices:

  • MC68EC000 CPU module 12.5Mhz
  • MC68EC060 CPU module 25Mhz
  • MC68681 (dual uart)
  • MC68230 (PIT port and timer)
  • DS7 (display 7 segment)
  • M48 (RTC)
  • 2/8MByte DRAM

i'm working around this devices

  • HD44780 (display 2x20 alphanumeric)
  • T6969 (display graphics)
  • I2C bus adapter PSX pad adapter
  • IDE-HD adapter new desin keyboard (developped around apple-newton-kb and dreamcast-jappanese-kb)

on the board i'm running

  • ucos/2 (it does not require a MMU, the 68EC000 has not, the 68060 has MMU and FPU)

An image of the board

M68ec0x0IDP.jpg

M68EC0x0 Integrated Development Platform version 3.1 July 1994

the board was made in 1992, and in 2002 costs $950, with a student reduce price i payed half the half: $250 ($90 surface shipping included) .


expanding RAM

Unfortunately the board is equipped with 2Mbyte of DRAM that can be expanded to 8Mbyte with this obsolete DRAM-array 1Mx32 (4Mbytes) for a total of 8Mbyte on board

- MCM54400AZ70 - MCM524256AZ70 package 100 MIL ZIP -

!!!!!!!!!!!!!!!!! ONLY ZIP PACKAGE !!!!!!!!!!!!!!!! 
MCM54400AZ70 ZIP pin assignments 


 * * * * * * * * * *
* * * * * * * * * * 


1 = !G 
2 = ! CAS 
3 = DQ2 
4 = DQ3 
5 = Vss 
6 = DQ0 
7 = DQ1 
8 = !W 
9 = !RAS 
10 = A9 
11 = A0 
12 = A1 
13 = A2 
14 = A3 
15 = Vcc 
16 = A4 
17 = A5 
18 = A6 
19 = A7 
20 = A8 

adding a peripheral: I/O module

The board has 6 x 16Mb addressable IDP buses: if the user wants to make a I/O module, the user should contact Motorola by writing to the address listed in "bus timing"

  • bus timing for information on M68EC0x0IDP bus timing, write the following adrress: Motorola High-Performance MPU division ATTN:
IDP Technical Support Mail Stop OE-33 6501 William Cannon Drive West 
Austin Texas 78735-8598 USA hi

clock sync

mc88915 or mc88916 is required in order to sync the module clock to the master clock

The meaning of DTACK Grounded

"DTACK" is

  • the name of a pin on the Motorolla 68000 CPU that informed the CPU that data was ready to be read from memory. If a system had fast enough memory, this pin could be connected directly to the ground plane (or "grounded") to produce the fastest-possible memory read time.
  • the signal from the memory system to the 68000 indicating “Yup, you can complete that memory cycle now,” and simply stapling it to ground means you’ve built a system with as few memory waits as you can.

I recall the DTACK Grounded boards were insanely expensive because they used a metric boatload of static RAM, but they ran as fast as raped apes


DTACK Revisited: fsm

the IDP bus requires a complex protocol, so a fsm machine is required in order to handle it: a cpld is fine for that

dynamic bus sizer

the IDP bus is 32bit, "mc68150" is a "dynamic bus sizer" chip made by Motorola for MC68040/MC68060: it may be a solution when you have a 32bit cpu and 8bit peripherals

Floating the Point

It was obvious from the first that while the 68000 was a really fast integer processor, it needed an FP math accelerator like the Intel 8087. Big M had in fact announced that it would ship such a part for the 68K in 1982, but it was vaporware until mid-1985.

Meanwhile, National Semiconductor developed a line of 68K-like processors, the 32000 series. NS used separate teams to develop the integer CPU and the FPU chips. The CPUs remained heavily bug-ridden for a long time. But when the 16032 FPU appeared in mid-1983, it worked.

Having learned from my original 68K experience, I carefully studied the 16032 data sheet and decided the FPU would (unlike Intel's 8087) easily interface with the 68K. So my little company built up a test jig using 3M's neat prototyping kit and guess what--it worked. But, unlike what the 16032 data sheet said, the FPU had to be run using a synchronous clock.

I published all this information in newsletter #24 (October 24, 1983), including a photograph of the prototype board. I contacted Stan Baker about this, and Stan's popular hardware column in Electronic Engineering Times reported that the 68K and the National Semi FP chip were compatible and a lot faster than Intel's x86 + 8087 combo. My next newsletter carried a photo and complete schematic of our second, simplified prototype. Soon we were selling production boards, one of which accepted up to three 16032s.

I thought Big M would be happy; FP support for the 68K now was readily available. Wrong. Big M folk were furious with me; they wanted everybody to wait for their 68881 to arrive. I thought National Semi would be happy because here was another market for its FP chip. Wrong. National Semi's minions were peeved because they didn't want its FPU used to support 68K-based systems. Intel was understandably unhappy. For a while there I screened my mail for letter bombs.

(National Semi told everybody that I didn't know what I was talking about; the 16032 was too an asynchronous part. Five months later, the data sheet was quietly changed to require synchronous operation. Tsk.)


proof

our motorola 68xxx dev board has a synch.bus.It can be handled only by a Finite State Machine (FSM) so we first look for a low cost CPLD/FPGA solution. too expensive, too much complicate. So now the project is based on a RAM-tiny-FSM: 4 input, 4 output, 16 states. The RAM is loaded with the bytestream at the boottime by a PIC that copy an I2C_EEPROM into the RAM. The project consists on the compiler (that make the bytestream image to be loaded to the eeprom, from a simil-C source) and the little board. I estimated that this TINY-FSM is able to work with a clock up to 25Mhz using old PC cache (15 ns) If you are interested we can collaborate about this project, about the hardware and about the software developping. Hello Adrian, It is nice to hear from you. I am glad that the 680x0 books I sent you are useful in your project. > i'm planning to develop a ROM/RAM tiny file-system What type of file system is this? Is it based on an existing file system such as MS-DOS, or something completely new? I have an interest in file systems, that is why I ask. FYI, the UCSD Pascal system has a very simple file system that support a fixed number of files (77). The file system is just a very simple array of file entries. Each file entry has a fixed width format similar to: file name (length byte + name characters) file type file creation date file modification date starting block ending block > the shell is ready as beta. > Would you like to try it under windows ? if so it will recompiled for > 80386 as a normal dos program. I would like to try this. Please compile for windows and let me know how to get it. Concerning the 680x0 IDP, try the following internet sites, they may have some information about this board's bus: http://www.faqs.org/faqs/motorola/68k-chips-faq/ http://archive.comlab.ox.ac.uk/cards/m68kfaq.html > a friend of mine went to Santa FE last weeks He should have contacted me, that would be fun. I live in Santa Fe in the north part. I have been here for about 10 years. Ciao >Subject: Re: Apple Lisa and Macintosh schematics >Date: Sun, May 25, 2003, 3:51 PM > HI !!!! luky to see you again ! > the book ? i'm developping a lot with "68000 family reference" > i'm programming a 680x0 emulator to deassembly with simulation path > .... yeh i'd like to hack and grap software secret to improve my > assembler. > I'm using my "68EC000 IDP board" rom with "MON68" monitor debugger > ..... my simultaor simulate the whole board using this rom. > In this way i can speed up download .... (that are reduced to a poor > file copy, because there is no real UART 9600 bps transfer .... just a > superfast 44MB/sec harddisk file copy .... the secret iis that the > memory is a file) > about hardware ? i'm planning to develop my board around a 68030, using > your "68030 reference book" ..... i'm planning just to use only 8bit > data bus ..... just 1 Kb Rom 1 64Kb Ram .... a HD44780 20x4 char > alphanumeric display and a 9600bps UART. > the firmware will be "PERVASIVE" : i mean that i'm planning to develop > a ROM/RAM tiny file-system, a nano kernel working with tasks (no > process or thread) ..... > well i'm learning a lot from your books .... i'm fully reading the SAMS > 68010-68020 primer .... that helps me a lot with the simulator > dettails. > wow that is all for now. > ah, yah i forget: the shell is ready as beta. > Would you like to try it under windows ? if so it will recompiled for > 80386 as a normal dos program. > I shocked myself porting it to my 68EC000 idp board .... and to a real > nintendo GameBoy > (this last one it was done for fun ..... i friend of mine told me that > was impossinble ..... but i did it) > any probelm ? > yes, to be honest a lot .... but the main one is that i have no > documentation about the bus of my "motorola 68EC0x0IDP integrated > development platform" ..... i bought it form Motorola (for $940) and > there is a documentation-book where it is written: > if you need documentation about the "IDP bus timing" please write to > "motorola Austin Texas" > i did as written nobody answared me .... i email motorola digitalDNA > .... the answared that the platform is obsoleted and that in their > server there is no documentation. > They suggest to use an oscilloscope to probe signal's timing from the > IDP bus ..... that is too hard for me for just a reason: i have no > oscilloscope .... and at school we have virtual one (done by LabView > and an acquisition board plugged inside PC) .... no goods for what i > need to do. > why i need this ? because the IDP bus is not standard and it is 25Mhz > syncronous ..... not so easy. > I'd like to plug an hard-disk to improve my file-system from tiny to > large (400MB 1GB) > that is really all since last time ... > and you ? how are you ? > a friend of mine went to SataFE last weeks ..... luky is him !!! > cool sun, cool place and people .... > and you what do you say ? > (p.s. where are you exactly ?) > best regards >>Hi Adrian, >>Have the Motorola 680x0 books been useful to your electrical engineering >>school work in Italia? Does the 68040 CPU chip work? Greetings, I haven't heard anything. I gave them your email address so you might get some mail directly. Also, I posted a request for the info on comp.sys.m68k Take a look: http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&group=comp.sys.m68k&selm=4163811b.0402201732.5b0d397%40posting.google.com So check this web page from time to time to see if someone replies. Good Luck, > hi, >> [*] bus timing > for information on M68EC0x0IDP bus timing, write the > >> following adrress: > >> Motorola > >> High-Performance MPU division > >> ATTN: IDP Technical Support > any news about this ??? > i can't find nothing on newsgroup. > Does your motorola friend have this information ? > or somebody know something about the board ? > best regards Greetings, Yes, I remember, how are you? Motorola is a very big company and the semiconductor division was just a small part. In fact, in the beginning it was set up to supply parts to the rest of the company. But it turned out that they sold most of their parts to other companies, and they made Motorola a lot of money for many years. But in the last several years the semiconductor division has been loosing money, so motorola decided to spin it off as a separate company. Now the must make money or go out of business! -mark- wrote: > hi, > do you remember me ? > i'm the boy you sold the "68060 die photos" > today i was shocked: "motorola semiconductors" has > been changed into "Freescale" > and all customers support of old "motorola digital > DNA" has automatically closed. what do you think is happening ? > is motorola in a big money jam ? > i contact the old "motorola digital DNA" to have informations about > "mc68150 dynamic bus sizer chip" freescale answared me ..... > (that it has no data-sheet) > what do you think ? > best regards I need precisely the functionality you are describing to test programs written for the ColdFire 5407 without the actual hardware. The code would only be used to create a tool for my use in testing and debugging my embedded code. My current project is an embedded system for testing proprietary electronic devices. Having an emulator would be invaluable during development and testing. If you could share your code with me I would certainly be willing to forward any support I add for the ColdFire back to you, if you like. If you can't share the actual code, I understand--I just had to ask--this sounds like it would be so helpful. Thanks, Chris -----Original Message----- Sent: Wednesday, September 03, 2003 3:00 PM Subject: Re: reverse assembler >Does your C program actually emulate the 68K? Yes, not the whole iset, i have to code it, i have no much time. However the demo i show to my teacher is able to run a "hello world" program that prints to a real HD44780 by re-defining trap 15 to a virtual device (that on the real board is a MC68230) that handles LPT where the display is attached. I planned to emulate 68000, 68020, 68030, 68040, 68060. I don't know how to handle MMU, now. however i'm working around 68000 and i have to test the ALU condition code register: there are no good tests in motorola books, i don't understand some dettails like MUL-U MUL-S condition code affections. >it sounds as if that is what you have--more than a mere disassembler. this because we code a lot of software, and because we did it aim for a lot of goal. The shell, the tini-filesystem and the "reverse-assembler" i don't like "disassembler" term because i mere de-asm is a program that jumps back your binary. My reverse-assembler emulate a binary into a virtual machine showing register contents step by step. I mean that i can obtain a file where you can easily track the register- values during the running. In this case the goal is the need: we have to code and test programs but we have to test them on a real 68000 board, the school's one, and unfortunatly we can't access to it when we want ... we have no much time and we have no money to buy a personal board. So we code an emulator to have the board in our portable PC. The real board is hard to be de-bugged ... because we can't track the memory or stop the CPU to analyze ... we code the emulator to allow this. >In your first post you asked if anyone was intrerested--if this is the case, >I am very interested--I need something like this to help me through my >>current project! what is your project about ??? how can my project help you ? which CPU should it be for ? >Would you consider sharing that code with me? it may be, i have to ask my teacher and my team. I remember you we are using ANSI crude C (borland Turbo C 3.0 for DOS) however the shell is portable to UNIX and we ported it using Gcc and HP-C89. what we really need now is a good 68K compiler. We hack Sierra C 68K, it works well but it is only for 68000, and it need windows. we will try to make a gcc-68K cross compiler for our HP-712 HPUX 11.00 best regards

Simulated Recursion

Recursion is a powerful tool for attacking problems where questions are repeated and the same actions are performed. C and Pascal allow recursion, but languages like COBOL generally forbid it.

In the early 1960s, C.A. Hoare developed the Quicksort sorting process. Quicksort divides the data into successively smaller groups. In itself this does not sound very impressive, but tests show that Quicksort can sort large volumes of data tens or hundreds of times faster than most commonly used algorithms. However, there is a problem.

Quicksort uses recursion, the process by which a procedure or a function calls itself. Recursion is very powerful in attacking problems where the same questions are repeated and the same actions are performed, but with each set of actions working with the result of a prior step. Examinations of data structures such as linked lists and trees are ideally suited for recursive programming. In languages such as C or Pascal, recursion is allowed, but languages like Cobol generally forbid recursion. A way around language limitations is to simulate recursion in a manner that can be coded in almost all programming languages.

A recursed program examines and acts upon data until it arrives at a point where logic suggests that there is a new set of data, ready to be acted upon by a new copy of the program being executed. At this point, the program calls itself. Normally this calling passes the new data to be processed by the next iteration. Eventually, the logic dictates that further recursion is unnecessary, and the current active version of the code falls out the bottom, returning to execute the instruction following the one that issued the call in the prior iteration of the recursive module. As each copy of the code finishes, it transmits information back to the calling copy. When control is finally passed to the original copy of the recursive module, falling out the bottom terminates the recursive process.

Simulating Recursion

Knowing the process by which recursion passes data upward and downward through the called modules, you can isolate and preserve the variables unique to each recursive step and simply loop a given piece of code to achieve simulated recursion. Since looping would start the code process at the same place each time, you must keep a place marker, indicating just where to begin the processing of the current iteration.

The data used by each iterative step can be in any form and is a function of the programming requirements. A binary switch is probably the best form for a place marker. A combination of the required variable data and a place marker form a snapshot of the conditions during any step of the recursion. You should construct a table where snapshots can be stored. A pointer to this stack of snapshots allows the program to select the appropriate set of values for a particular iteration of the recursive process. The depth of the stack must be such that it can contain all the steps necessary to achieve the objective of the program being executed.

Simulated Recursion in Quicksort Example

The examples I present here demonstrate simulated recursion Quicksort in a Cobol program. This is one of the most hostile and awkward environments in which to do recursive programming. The idea is, "If we can do it here, we can do it anywhere." The data portion of Quicksort would look like Listing One.

In Listing One, a table of 32,000 100-byte entries is the data to be sorted. SWAP-ELEMENT and PIVOT-VALUE represent scratch work areas required to hold individual table entries from time to time. The WORKING-INDEXES point to table entries and, as such, are full-word integers. FURST and LAAST are pointers to the first and last table entries in a group currently under consideration. The size and location of that group changes constantly during the progress of Quicksort.

HOW-RETURN is the place marker enabling the program to begin processing at the correct place when reentering the looped code. The place-marker concept is critical to enabling fixed, looped code to emulate recursive processing.

The TABLE-OF-INDEXES is a stack of WORKING-INDEXES. As the program progresses downward (calling another iteration of QUICKSORT) or upward (returning to a prior iteration) the values for pointers and place markers are saved or retrieved. Every occurrence within the TABLE-OF-INDEXES is one set of WORKING-INDEXES. The SESSION-INDEX is the pointer to the set of values currently being used. LEFT and RIGHT-INDEX are working pointers used during each phase of Quicksort.

Listing Two initializes Quicksort. It presets the stack of working pointers to binary zero bits. Then, one set of working pointers is initialized, with the FURST pointer set to point to the first element in the data to be sorted and LAAST set to point to the last. Setting the HOW-RETURN switch to 1 indicates that this is a new iteration of the Quicksort code and processing should begin at the beginning. The SESSION-INDEX is set to 1 (this will be the first session) and the data is loaded onto the stack.

Each iteration of the code in Listing Three first pulls data from the stack and then puts it into the WORKING-INDEXES. The value of the SESSION-INDEX determines which data is pulled. By controlling the values for the SESSION-INDEX and the HOW-RETURN switch, you control how each program loop functions.

The program logic in Listing Four examines a specific group of table elements. Even though the members under consideration change continually, the examination process is exactly the same; hence the application of recursive processing.

The program logic establishes the first element to be a pivot point around which other comparisons will be made. Elements are examined from left to right, and from right to left, and element swaps are made where indicated. The end result is that the pivot element has been relocated and now divides the group into two smaller groups, where all elements to the left of the pivot are smaller than the pivot, and all elements to the right are larger. This produces two new, smaller groups that are then examined in the same manner.

Listing Five prepares the Quicksort environment to examine first the left side, and then the right side of the two newly created strings of data to be sorted. When the index values have been set, the program simply calls Quicksort again. After Quicksort examines both strings and returns control to this iteration of the code, the program tests to see if this iteration is the first one that initiated the sort. If that is the case, the sort is complete. If not, the pointer to session data is reduced by one and, in effect, when Quicksort is called again (see Listing Six), control is returned to the prior program iteration.

What is the difference between a typical user sort, where every element is compared against every other element, and a recursive Quicksort? In large volume sorting operations, the differences are impressive. Recursive Quicksort could mean saving minutes or even hours when sorting large amounts of data. The recursive process is very powerful and has many uses in mathematical analysis. Quicksort is only one application of this type of programming logic.

Conclusion

While this example illustrates the use of a simulated recursion Quicksort in Cobol, this process can be used in many other types of languages including C and Pascal. The use of the recursive Quicksort can greatly reduce the time needed to sort large amounts of data, which can be useful regardless of the programming language.

DDJ

Listing One

 01  TABLE-TO-BE-SORTED.
     02 TABLE-ENTRY   PIC X(100) OCCURS 32000 TIMES.
*
 01  SWAP-ELEMENT     PIC X(100).
 01  PIVOT-VALUE      PIC X(100).
*
 01  WORKING-INDEXES.
     02 FURST         PIC 9(5) USAGE BINARY.
     02 LAAST         PIC 9(5) USAGE BINARY.
     02 PIVOT         PIC 9(5) USAGE BINARY.
     02 HOW-RETURN    PIC 9(5) USAGE BINARY.
*
 01  TABLE-OF-INDEXES.
     02 CURRENT-INDEXES OCCURS 100 TIMES.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
         03 FILLER    PIC 9(5) USAGE BINARY.
 01  SESSION-INDEX    PIC 9(5) USAGE BINARY.
*
 01  LEFT-INDEX       PIC 9(5) USAGE BINARY.
 01  RIGHT-INDEX      PIC 9(5) USAGE BINARY.

Back to Article

Listing Two

 INITIALIZE-SORT.

     MOVE LOW-VALUES TO TABLE-OF-INDEXES.
     MOVE 1 TO FURST
               HOW-RETURN
               SESSION-INDEX.
     MOVE 32000 TO LAAST.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).

Back to Article

Listing Three

CALL-QUICKSORT.
     MOVE CURRENT-INDEXES (SESSION-INDEX) TO
         WORKING-INDEXES.
     IF HOW-RETURN = 2 GO TO DO-PIVOT-TO-LAST.
     IF HOW-RETURN = 3 GO TO SEE-IF-WE-ARE-ALL-DONE.
     IF FURST NOT < LAAST GO TO SEE-IF-WE-ARE-ALL-DONE.

Back to Article

Listing Four

 SPLIT-THE-LIST.
     MOVE TABLE-ENTRY (FURST) TO PIVOT-VALUE.
     MOVE FURST TO LEFT-INDEX.
     COMPUTE RIGHT-INDEX = LAAST + 1.
     PERFORM WITH TEST AFTER UNTIL
             RIGHT-INDEX <= LEFT-INDEX
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (LEFT-INDEX) >= PIVOT-VALUE
             ADD 1 TO LEFT-INDEX
         END-PERFORM
         PERFORM WITH TEST AFTER UNTIL
             TABLE-ENTRY (RIGHT-INDEX) <= PIVOT-VALUE
             SUBTRACT 1 FROM RIGHT-INDEX
         END-PERFORM
         IF LEFT-INDEX < RIGHT-INDEX
             PERFORM EXCHANGE-TWO-ELEMENTS
         END-IF
     END-PERFORM.
     MOVE FURST TO LEFT-INDEX.
 EXCHANGE-TWO-ELEMENTS.
     MOVE TABLE-ENTRY (LEFT-INDEX) TO ENTRY-HOLDER.
     MOVE TABLE-ENTRY (RIGHT-INDEX) TO
          TABLE-ENTRY (LEFT-INDEX).
     MOVE ENTRY-HOLDER TO TABLE-ENTRY (RIGHT-INDEX).
 EXCHANGE-TWO-ELEMENTS-EXIT.
     MOVE RIGHT-INDEX TO PIVOT.


Listing Five

 DO-FIRST-TO-PIVOT.
     MOVE 2 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE LAAST = PIVOT - 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUICKSORT.

*
 DO-PIVOT-TO-LAST.
     MOVE 3 TO HOW-RETURN.
     MOVE WORKING-INDEXES TO 
         CURRENT-INDEXES (SESSION-INDEX).
     COMPUTE FURST = PIVOT + 1.
     MOVE 1 TO HOW-RETURN.
     ADD 1 TO SESSION-INDEX.
     MOVE WORKING-INDEXES TO
         CURRENT-INDEXES (SESSION-INDEX).
     GO TO CALL-QUICKSORT.


Listing Six

*
 SEE-IF-WE-ARE-ALL-DONE.
     SUBTRACT 1 FROM SESSION-INDEX.
     IF SESSION-INDEX > 0
         GO TO CALL-QUICKSORT.
     STOP RUN.


the m68k

ebook

http://www.toodoc.com/mc68008-ebook.html


mc68020 brief

Motorola 68020 (MC68020) is a 32-bit microprocessor compatible with earlier members of 680x0 family - 68000, 68008 and 68010. Address bus width on the 68020 is increased to 32 bits, which allows the processor to address up to 4 GB of memory. Data bus width is also increased to 32 bits, though if necessary the 68020 can work with 8- and 16-bit data buses. Other Motorola 68020 enhancements include:

  • Execution time of many instructions was reduced.
  • To improve CPU performance, a 256-byte instruction cache was added to the CPU.
  • The CPU includes new control registers.
  • The CPU has new addressing modes: memory indirect addressing modes, scaled index, and larger displacements.
  • New instructions were added to 68020 instruction set: bit field instructions, compare instructions, call module and pack/unpack BCD.
  • The MC68020 provides hardware support for Motorola 68881 and 68882 Floating-Point Units.
  • Accessing mis-aligned word or long-word data no longer results in a system error, though access to misaligned data is not as fast as access to properly aligned data.

Motorola also manufactured MC68EC020 - embedded version of the MC68020 CPU. The 68EC020 had only 24-bit address bus, and could address up to 16 MB of physical memory. The MC68EC020 was housed in different packages than the Motorola 68020 microprocessor.


model: clock.min: clock.max:

MC68000/008/010 FAQ

Is it okay to tie the HALT* and RESET* lines together on the MC68000 together?

Tying HALT* and RESET* together will not cause any problems for the MC68000.As you probably know, RESET* on the MC68000 should never be asserted without asserting HALT* as well. You must realize, however, that tying the two lines together introduces the following three restrictions:

  • 1 You can not do hardware single-stepping of the processor.
  • 2 You can not perform a retry.
  • 3 The processor will reset itself if you get a double bus error (by asserting HALT*).

Many systems can function within the bounds of the above restrictions and operate without problems when HALT* and RESET* are tied together.

Should I assert RESET* on the MC68000 without asserting HALT* as well?

On the MC68000/MC68EC000/MC68008 processors, RESET* should never be asserted without asserting HALT* as well. You may bring about the assertion of HALT* with RESET* through external logic or by tying the two lines together. You must realize, however, that tying the two lines together introduces the following three restrictions:

  • 1 You can not do hardware single-stepping of the processor.
  • 2 You cannot perform a retry.
  • 3 The processor will reset itself if you get a double bus error (by asserting HALT*).

Is it okay to assert the MC68000 VPA* and DTACK* inputs at the same time?

DTACK* should never be asserted while VPA* is asserted. Asserting DTACK* and VPA* at the same time will produce unpredictable results.


Will the MC68000 support 4 megabytes of DRAM using 1x9 1-Mbyte SIMMs?

You should have no problems interfacing standard DRAM SIMMs to the MC68000.Note that the MC68000 does not burst so you do not need any special type of DRAM such as page-mode DRAM which would normally be required to support bursting.


What kind of cache design would you recommend for the MC68000?

A system can be designed around an MC68000 which uses relatively cheap (80 ns or 100 ns) DRAM and yet provides zero wait-state accesses. Therefore, we do not recommend using a cache with the MC68000.


How do you perform a long-word write with an MC68000 with a 16-bit bus?

The MC68000 instruction set supports long-word moves. When the processor executes an instruction that calls for a long-word write, it will perform two 16-bit writes. Note that bus arbitration is done on a cycle-by-cycle basis, so the bus can be arbitrated away from the MC68000 after the first of the two 16-bit writes, and the processor will complete the long-word write after it retakes the bus.


What is the difference between an MC68000 and an MC68008?

  • 1 The MC68000 is a 16-bit processor, whereas the MC68008 is an 8-bit processor.
  • 2 Therefore, UDS* and LDS* on the MC68000 are replaced by DS* and A0 on the MC68008.
  • 3 The MC68008 uses two-wire bus arbitration, whereas the MC68000 uses three-wire bus arbitration.
  • 4 The MC68000 supports three interrupt lines and, therefore, seven interrupt levels. The MC68008 supports only two interrupt lines and, therefore, three interrupt levels. The MC68008 PLCC package supports three interrupt lines like the MC68000.
  • 5 The MC68000 provides 16 Mbytes of addressable space. The MC68008 has 20 address lines creating 1 Mbyte of addressable space. The MC68008 PLCC package has 21 address lines for 2 Mbytes of addressable space.
  • 6 The MC68008 does not have a VMA* signal as does the MC68000, but this signal can be generated with some simple external logic (see M68000 Users Manual (M68000UM/AD)).
  • 7 The MC68000 and MC68008 are not pin compatible.

It should be noted that the MC68EC000 provides a lower cost solution compared to the MC68008 and is available at more frequencies than the MC68008. The MC68EC000 can operate in either 8-bit or 16-bit mode and does not include the 6800 peripheral interface, but is virtually identical to the MC68000 in every other way. If you are planning to do a design with the MC68008, it would be worth your time to consider the option of using the MC68EC000 instead.

During a byte access on the MC68000, which bits of the data bus are read/written?

If the MC68000 asserts UDS*, then bits 15-8 of the data bus will be used. If the MC68000 asserts LDS*, then bits 7-0 of the data bus will be used.

The MC68230 is an 8-bit peripheral. On which byte lane of the MC68000 should I place the MC68230?

The MC68230 should be placed on the lower byte lane (i.e., on data bits 7- 0) of the MC68000. This is required because when the MC68230 provides an interrupt vector for the MC68000 it must be right-aligned. In all other respects, the two byte lanes of the MC68000 would be equally qualified for attaching the MC68230. Note that your software must be written so that all accesses to the MC68230 are byte accesses to even addresses to make sure the proper byte lane (bits 7-0) of the MC68000 are used.


What is the state of AS* during reset on the MC68000 and how long after reset before AS* becomes valid?

AS* remains inactive during reset. It will take an undetermined amount of time after reset before AS* will become valid. However, if you are not getting an AS* after you come out of reset, you should check the following signals:

  • 1 Check to make sure BR* and BGACK* are negated to make sure you are not arbitrating the bus away from the MC68000.
  • 2 Check to make sure HALT* is negated.

Intel has a pin that allows the signals to tri-state. Does the MC68000 have something similar?

Motorola does not provide such a pin. However, if you want to cause the signals from the MC68000 to tri-state, you can arbitrate the bus away from the MC68000 which will cause it to tri-state all signals with the exception of the bus arbitration signals.


In an MC68000 system, we desire that all registers of an 8-bit peripheral be mapped on byte boundaries. How can we do this?

Essentially, what is needed is pseudo-"dynamic bus sizing." This feature is implemented on the MC68020 and MC68030, but not on the MC68000. There is no glueless way of implementing dynamic bus sizing on the MC68000. The cheapest solution is to place the peripheral on one of the byte lanes and use the MOVEP instruction. The UDS/LDS signals will uniquely determine the byte of the data bus.


What is the interrupt latency for the MC68000 family?

Interrupt latency is the time from when an interrupt occurs to when the first instruction of the interrupt handler is started. The amount of time required for this will depend the processor, what the processor is doing when the interrupt occurs, and the speed with which the memory responds to reads and writes.

Worst case interrupt latency is the absolute maximum amount of time it will take for the processor to respond to the interrupt for a given set of conditions. A given interrupt may respond sooner (and usually will), but it will never take longer. The selection of the conditions can have a major impact on the interrupt latency. For example, the number of wait states on writes will effect the time it takes to stack the interrupt stack frame. An infinite number of wait states on writes would result in an infinite interrupt latency.

The following lists the interrupt latency for a given processor and the conditions assumed.

MPU           Conditions                                     Latency
MC68EC000     MOVEM.L xxx.L,D0-D7/A0-A7
16-bit        DIVS xxx.L, Dn
data bus      interrupt at beginning of MOVEM                378 
clks

MC68EC000     MOVEM.L xxx.L,D0-D7/A0-A7
8-bit         DIVS xxx.L, Dn
data bus      interrupt at beginning of MOVEM                574 
clks

MC68EC020     MOVEM.L <memory indirect ea>,D0-D7/A0-A7
MC68EC030     interrupt at the beginning of MOVEM            197 
clks
32-bit bus    no bus errors

MC68EC040     any integer instruction stream,
              no back-to back 64-bit divide instructions
              no CAS,TAS,CAS2 instructions                    78 
clks

How many transistors are on each of the MC68000 family devices?

DEVICE          TRANSISTORS

MC68000           68,000
MC68EC000         68,000
MC68HC000         68,000
MC68HC001         68,000
MC68008           70,000
MC68010           84,000
MC68020          190,000
MC68EC020        190,000
MC68030          273,000
MC68EC030        251,000
MC68040        1,170,000
MC68EC040        962,000
MC68LC040        813,500
MC68230           16,700
MC68302          320,000
MC68330          235,000
MC68340          350,000
MC68440           26,000
MC68450           40,000
MC68451           34,000
MC68661            6,000
MC68681            9,743
MC68851          210,000
MC68881          155,000
MC68882          176,000
MC68901            9,100


If BR* is asserted before RESET* negates, when will the MC68HC000 take control of the bus?

If BR* is asserted when the MC68HC000 comes out of reset, it will assert BG* in order to grant the bus to the requesting device. The requesting device will then most likely respond with BGACK*. The MC68HC000 will not take back the bus until BR* and BGACK* are both negated.