pratt%Navajo@.ARPA (05/02/85)
From: coraki!pratt@Navajo (Vaughan Pratt) A hearty hear-hear for Peter Barada's praise of the PDP-8. Here's a PDP-8 story I never got around to telling, but which in retrospect was a fun project. At Sydney University in 1969 I wanted a workstation (by concept, not by name, the word "workstation" didn't appear till the 1980's) on which to do my Master's thesis project. The only candidate was a 4K PDP-8 purchased ostensibly as a $10K cog in a $50K wheel consisting of a 338 vector display system. Simultaneously a psychology Ph.D. student and I independently realized that it would be perfect for our respective projects, his to run experiments monitoring interference between human video and audio channels, mine to write an interactive solver of syllogisms of the kind Lewis Carroll used to publish in newspapers. We agreed that he would have it for the mornings and I for the afternoons. When it became clear that my project would not fit, I reduced its scope to mere translation of English syllogisms into conjunctive normal form, ready for input into a ground-resolution theorem prover (which I would have written to turn the project into a Ph.D. thesis had I stayed at Sydney). The final program ran entirely within the 4K PDP8 (no overlays), using a Model 33 10-cps teletype as its only peripheral. Code and data storage was split 50/50. Here's the breakdown of memory, with rough sizes. Modules: Operating System Bootstrap Loader (20) Load-and-go Assembler (homebrew) (160) Debugger (ODT) (400?) Interrupt handler (for parallel reading and printing) (90) Datatype runtimes String package (100) List package (cons/car/cdr + "manual" GC) (128) Sparse matrix package (for Younger's algorithm) (200) Natural language Lexical analysis (80) Parser (Younger's algorithm) (200) Syntax-directed translator (450) Logic AND-OR-NOT for CNF expressions (160) Databases: Dictionary: ~150 "closed-class" words (prep., pron.,conj.,adv.) (500) Affixes: ~20 prefixes and suffixes Grammar: 156 productions (300) Semantics: one expression per production, in RPN (250) Work Areas: I/O and string buffers: 256 Younger matrix: 500 Free list space: 200 n-word sentences were parsed at .007n**2 seconds, always. (The n**3 bound for Younger's algorithm is worst case, expect n**2 for typical grammars of English.) For each parse the output consisted of a list of phrases from the sentence each labelled with a letter, and a conjunctive normal form formula using those letters. Its biggest problem was that it would sometimes find half a dozen parses of a sentence, not all yielding the same output, a problem I did not deal with. For about 3/4 of the 200 sentences in Carroll's collection of syllogisms, at least one of the parses would yield the correct output. The main problem here was lack of time for tuning the grammar. The program did much better than I expected in figuring out the parts of speech of open class words (nouns, verbs, adjectives) it had not seen before. Near the end of the project I found myself squeezing in additional instructions by patching in jumps to pages where there were still a few empty words. No way was this program ever going to get additional functionality without getting another 4K! That reminds me, I need to get another megabyte for my Sun, 2Mb is too small for big Franz packages. -v
peterb@pbear.UUCP (05/06/85)
Thanx for the applause. I like it. (your story that is :-). What I would like to see is a proposal of a "next generation" PDP-8, Something with say: 16 bit memory 65K fields 256 fields (yields 24Mb memory) each field broken to 256 256 word pages direct addressing mode (so arryas and stuff don't have to be paged) built in extended AU other goodies. Oh Yeah, a stack would be quite useful. This type of architecture would encourage (NOT force) the programmer to write localized code for his routines. Also language compilers would be designed to take advantage of this concept. Also VM overhead would be smaller since the locality of page operations would keep paging activity lower than say a VAX. In fact I would not be suprised if this type of architecture could beat a VAX in terms of (probably fit in less memory and run faster :-) Any Ideas??? Peter Barada ima!pbear!peterb ihnp4!inmet!pbear!peterb I welcome contructive ideas, but If you are going to flame me for thinking of such a monstrosity, snuff it!
peterb@pbear.UUCP (05/07/85)
Oops, ED chopped a line out of my previous response. After "Probably beat a VAX in terms of" add: Paging overhead and size of workspace. Sorry for the omission. Peter Barada / ima!pbear!peterb / ihnp4!inmet!pbear!peterb
henry@utzoo.UUCP (Henry Spencer) (05/10/85)
> What I would like to see is a proposal of a "next generation" PDP-8, > > Something with say: > > 16 bit memory > 65K fields > 256 fields (yields 24Mb memory) > each field broken to 256 256 word pages > direct addressing mode (so arryas and stuff don't have to be paged) > built in extended AU > other goodies. > > Oh Yeah, a stack would be quite useful. To a sloppy first approximation, if you squint a lot, the Intel 8086 meets these specs. Yuck. 16-bit address spaces are the pits, even if you have lots of them. > This type of architecture would encourage (NOT force) the programmer to > write localized code for his routines. Also language compilers would be > designed to take advantage of this concept. You mean "language compilers could be designed, at horrendous cost in pain and effort, to take advantage of this concept". Page boundaries and field boundaries are the two massive headaches in building a decent pdp8 compiler; I studied this for a while years ago. "There just ain't no graceful way." -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,linus,decvax}!utzoo!henry
doug@terak.UUCP (Doug Pardee) (05/11/85)
> 16 bit memory > 65K fields > 256 fields (yields 24Mb memory) > each field broken to 256 256 word pages > direct addressing mode (so arryas and stuff don't have to be paged) > built in extended AU > other goodies. > > Oh Yeah, a stack would be quite useful. Almost sounds like my recollection of the (mythical) Western Design Center WDC65SC816, the 16-bit extension of the 6502. Also, you can treat the NS32000 CPUs pretty much that way, but not with the standard assembler unless you like to code repetitive options on every instruction. The assembler was written by an HLL weenie who couldn't imagine using the registers in any non-HLL, non-relocatable fashion. -- Doug Pardee -- Terak Corp. -- !{ihnp4,seismo,decvax}!noao!terak!doug ^^^^^--- soon to be CalComp
srm@nsc.UUCP (Richard Mateosian) (05/11/85)
In article <3500002@pbear.UUCP> peterb@pbear.UUCP writes: > >What I would like to see is a proposal of a "next generation" PDP-8, > > 16 bit memory > 65K fields > 256 fields (yields 24Mb memory) > each field broken to 256 256 word pages > direct addressing mode (so arryas and stuff don't have to be paged) > built in extended AU > other goodies. > > Oh Yeah, a stack would be quite useful. > >Any Ideas??? Sounds a lot like a Z8000 (Z8000 + Z8015, to be precise), except that the Z8000 also has a decent register set. -- Richard Mateosian {allegra,cbosgd,decwrl,hplabs,ihnp4,seismo}!nsc!srm nsc!srm@decwrl.ARPA
heiss@spp2.UUCP (Robert Heiss) (05/13/85)
In article <3500002@pbear.UUCP> peterb@pbear.UUCP writes: > >What I would like to see is a proposal of a "next generation" PDP-8, > >Something with say: > > 16 bit memory > 65K fields > 256 fields (yields 24Mb memory) > each field broken to 256 256 word pages > direct addressing mode (so arryas and stuff don't have to be paged) > built in extended AU > other goodies. Look at the 65816 microprocessor. Except for the relative addressing on short branches, its architecture is similar to your description. > Oh Yeah, a stack would be quite useful. But not a *paged* stack. If your hardware can only support a 256 byte stack, why bother? To support high-level language, you could emulate a real stack by using indirect addressing (ala PDP-8, NOVA, APPLE ][). >This type of architecture would encourage (NOT force) the programmer to >write localized code for his routines. Also language compilers would be >designed to take advantage of this concept. > >Also VM overhead would be smaller since the locality of page operations >would keep paging activity lower than say a VAX. In fact I would not >be suprised if this type of architecture could beat a VAX in terms of > > (probably fit in less memory and run faster :-) > >Peter Barada I'm intrigued by the VM overhead argument -- a paged-address-space CPU connected to virtual memory with the same fixed page size -- has this experiment been performed? Coming soon: Paged RISC + VM vs. MicroVAX II Any volunteers to write a paged-memory C compiler? :-) -Robert !ihnp4!trwrb!trwspp!spp2!heiss
herbie@watdcsu.UUCP (Herb Chong [DCS]) (05/17/85)
In article <590@spp2.UUCP> heiss@spp2.UUCP (Robert Heiss) writes: >I'm intrigued by the VM overhead argument -- a paged-address-space CPU >connected to virtual memory with the same fixed page size -- has this >experiment been performed? i may be misunderstanding what you are suggesting, but doesn't the IBM S/370 and 370-XA architecture do exactly this? hardware pagesize is 4K and the "priviledged" instructions for page manipulation work with 4K pages. Herb Chong... I'm user-friendly -- I don't byte, I nybble.... UUCP: {decvax|utzoo|ihnp4|allegra|clyde}!watmath!water!watdcsu!herbie CSNET: herbie%watdcsu@waterloo.csnet ARPA: herbie%watdcsu%waterloo.csnet@csnet-relay.arpa NETNORTH, BITNET, EARN: herbie@watdcs, herbie@watdcsu