1
\$\begingroup\$

A friend of mine came up with an idea for something dealing with a micro-processor running C natively. Problem is, we need to be able to know if there is a processor out there already before we spend our time and money on something. Does anybody have any clue about such a processor?

\$\endgroup\$
  • 7
    \$\begingroup\$ "running C natively"... what does that even mean? C is a compiled language \$\endgroup\$ – vicatcu Sep 25 '12 at 16:29
  • 3
    \$\begingroup\$ A C compiler implemented in hardware... interesting =P \$\endgroup\$ – NickHalden Sep 25 '12 at 16:39
  • 2
    \$\begingroup\$ @David - Could you write an answer about the practical pitfalls of such a project, and why it's impossible? I have an idea, but it would be good to hear from the expert. :-) \$\endgroup\$ – stevenvh Sep 25 '12 at 16:59
  • 5
    \$\begingroup\$ @CodeAdmiral I hope I don't sound disrespectful, but I'd recommend that you actually make a processor of some kind on a say FPGA and see how complex that is. Then evaluate feasibility of making a C-executing processor. Don't forget that after that (if the results of previous step are positive), you also need to figure out how to convince others that 1. you're serious, 2. the execution of C is in fact better than executing a compiled machine code 3. what are you going to do when a new version of C standard comes and 4. what happens when C loses popularity. \$\endgroup\$ – AndrejaKo Sep 25 '12 at 17:00
  • 1
    \$\begingroup\$ @CodeAdmiral That's my opinion. Don't let me get in your way of becoming filthy rich :-) As I see it, designing a microprocessor is a very complex task. Designing a compiler is a very complex task. And you want to combine the two.. \$\endgroup\$ – m.Alin Sep 25 '12 at 17:02
18
\$\begingroup\$

Of course to properly look at this we must know what it means to "Natively" execute anything. On the surface this seems like an easy question, but it isn't. Let me elaborate.

But first, let me say that I am massively simplifying this description! There is no way I can explain this in a reasonable number of words without some over-arching generalizations and simplifications. Deal with it.

Let's start with a bit-slice processor (BSP) design. These are the easiest of processors to design, the hardest to program for, the smallest in terms of logic size, and the worst in terms of code-density. Essentially, an instruction word in a bit-slice processor never goes through an instruction decode step. The instruction word is somewhat pre-decoded. The individual bits of the instruction goes directly to latches, muxes, ALUs, etc inside the processor. Consequently the instruction word can be very large. Instructions larger than 256 bits is not uncommon! Normal BSP's are purpose built for a single task and are not general purpose CPU's. While BSP's sound somewhat exotic, they are used all over the place but are so deeply embedded that you probably don't notice.

One step up from a BSP is a RISC CPU. The overall data flow is changed to be more general purpose, and an instruction decode stage is added to the pipeline. Inside the RISC CPU there is still a giant instuction word, like the BSP, except that the instruction decode is used to convert the 32-bit instruction into that giant instruction word. Fundamentally this instruction decode is like a giant look up table that converts the 32-bit instruction to the giant instruction word used in the BSP. It is not literally a giant look up table, but that is what it effectively is. This instruction decode limits what the instructions can do, but greatly simplifies programming and is what turns this thing into a general purpose CPU.

Next step up we get to a CISC CPU. The main difference is that the instruction decode becomes more complex. Instead of the ID being just a huge lookup table, the ID converts the 32-bit instruction into a series of BSP-like instructions. You can really think of each 32-bit instruction and being a small subroutine call inside a BSP.

Next, you have assembly language. This is the ASCII text that you write that gets converted into those 32-bit instructions by the assembler and linker. While this is the lowest level of programming that a human might do, there is not always a one to one relationship between what the human writes and what the CPU executes. Even here the assembler is doing some level of interpreting and manipulating of the final instructions. For example, MIPS assemblers will rearrange or add instructions to deal with pipeline hazards. I'm sure other assemblers will do something similar.

Then you have a fully interpreted language. In this language, the interpreter has to parse the ASCII of each line or command every time that line is executed. This is what most scripting languages do.

There are also fully compiled languages, like C/C++, in which a compiler takes the ASCII source code and converts it into assembly language (or sometimes directly into the normal 32-bit opcodes).

Between interpreted and compiled languages there is "tokenized languages". These are most like interpreted languages, but the ASCII source code is parsed only once. The net effect is that the execution speed is much quicker and a fully interpreted language, but you still have the flexibility of an interpreted language and don't have the compile time of a compiled language. The term "tokenized" is used because the code is pre-parsed, or tokenized, into something that is easier to deal with than straight ASCII. Java is a good example of a tokenized language.

There have also been "BASIC CPUs", essentially these are CPU's that have a BASIC interpreter built into them. They are a normal MCU where the Flash EPROM contains a BASIC interpreter as well as the pre-tokenized BASIC program.

So, back to the question: What does it mean to natively execute a program? Does the program have to be down to the BSP level to be native? If so then almost nothing is native. What about the 32-bit instruction level? Ok, that's what most would call native since that is what the "CPU block" is given to execute. Normally anything ASCII is not "native" since some level of interpretation needs to be done before it can be executed. How about those BASIC MCU's? Do they natively execute BASIC? Probably not.

But let's look more at those BASIC MCU's. The BASIC interpreter is stored in the Flash EPROM and is made up of those MCU's standard opcodes. But what if the interpreter was actually part of a CISC CPU's instruction decode? Instead of the instruction decode running some subroutine for an "Multiple and ADD with Saturation" instruction, it ran a subroutine for "let X=5 + y". Would that CPU then be said to execute BASIC natively? I would!

But let's look at the C language specifically. And let's assume some crazy CISC processor that would interpret ASCII C source code directly. As you look at the tasks of managing files, parsing ASCII, and managing variables you notice two things: Either the BSP at the core of our C-CPU becomes absolutely huge and unmanageable or the BSP starts to look like what any other modern CPU has. But if the BSP looks similar to other CPU's then the instruction decode must do all the hard work, which it is not well suited for either.

What you end up with if you follow this to it's natural conclusion is something that looks like a normal RISC or CISC CPU that has a C Interpreter already programmed into it's Flash EPROM. Exactly like those Basic MCU's I mentioned before!

The net result is that a CPU that runs C "natively" is not useful-- even as an educational project. I could go on and on, but I'm almost late for a meeting now. Enjoy!

\$\endgroup\$
  • \$\begingroup\$ Indeed. The dividing line between implementing the published processor instruction set in microcode, vs having a language "interpreter" in ROM is ultimately as much about how we think about the device or how much is exposed to the developer as how it actually works. \$\endgroup\$ – Chris Stratton Sep 25 '12 at 21:28
  • \$\begingroup\$ Well said. +10 if I could. \$\endgroup\$ – Olin Lathrop Sep 26 '12 at 13:46
  • 2
    \$\begingroup\$ Thanks for taking the time to write this extensive answer. +1 \$\endgroup\$ – stevenvh Sep 26 '12 at 14:16
10
\$\begingroup\$

If by "native" you mean injecting the source code as a stream of ASCII characters to be logically decoded by the low-level logic, then forget it. Such a processor would have several orders of magnitude the complexity of current processors: you don't only have to detect the 64-bit pattern representing the variable "filename", but it can appear anywhere in the code as well. The same variable name will appear dozens of times in the code, and the matching logic must link all those to the same memory locations. And it must work for longer variable names as well, just any variable name. Just to name one issue.

Not only would the controller be a lot more complex, it would also need 100 kBytes to store the program which in compiled form only needs a a few kBytes.

One reason there are compilers to create machine code is to reduce any level of source code complexity to a limited set of simple instructions, so that it can be executed by a limited amount of logic. You can write an infinite number of different C programs, and you can't even guarantee that the processor will be able to execute "hello world".

\$\endgroup\$
  • 1
    \$\begingroup\$ "The "Hello world" program may need".. Don't leave us hanging.. :-) \$\endgroup\$ – m.Alin Sep 25 '12 at 16:53
  • 1
    \$\begingroup\$ @m.Alin - Just checking if you were paying attention :-). \$\endgroup\$ – stevenvh Sep 25 '12 at 16:55
  • \$\begingroup\$ I doubt that this is several order of magnitude more complex than current processors. Some of the branch prediction and out-or-order execution stuff is awfully involved. Actually, much of the behavior of parsing and lexing maps very well to hardware (finite state machines everywhere). But neither is it a level of complexity that a small team could hope to implement. \$\endgroup\$ – Ben Voigt Sep 25 '12 at 17:59
  • \$\begingroup\$ @Ben - But how about a simple thing like matching a variable name, an unknown string of unknown length, and it may appear anywhere in memory. So Your logic has to find a way to match the bytes 1456 through 1463 with 7811 through 7818, but it should also be able to match that if either is 1 byte, or 10 bytes, or 100 bytes further. How are you going to do that? \$\endgroup\$ – stevenvh Sep 25 '12 at 18:07
  • \$\begingroup\$ @stevenvh: Nobody does that (determine that this identifier matches that source code over there), not compilers, not interpreters, and not hardware implementations. You can build a symbol table just like the compiler does, except you have tools like content-addressable memories to improve performance. Also remember that the C standard allows really long identifiers, but allows an implementation to require uniqueness of a short prefix (14 characters or so). \$\endgroup\$ – Ben Voigt Sep 25 '12 at 18:24
9
\$\begingroup\$

Processors don't even run on Assembly language as you seem to think. They run on machine code. There is no "native" language of the processor. There are only its raw guts: registers, logic, data buses, multiplexers, memory.

\$\endgroup\$
  • \$\begingroup\$ In many cases, there's a 1-1 correspondence between assembly and machine language, with the former simply being a little more human-friendly - symbolic names, automatic assignment of addresses, macro expansion, etc. Sometimes it can get more complicated, but sometimes it really is that simple. \$\endgroup\$ – Chris Stratton Sep 25 '12 at 21:20
  • 1
    \$\begingroup\$ +1 Assemblers still need to "compile" and "link" assembler code to machine code, and machine code is often represented in microcode. There is a vast difference between assembler and what code flows through the CPU \$\endgroup\$ – TFD Sep 26 '12 at 3:53
  • \$\begingroup\$ For RISC processors, there is very little difference between assembly code and machine code. If you don't believe me, take a binary code file and run it through a disassembler and tell me the resulting assembly is not precisely what the CPU is executing. For CISC processors this is a different story, micro-ops and all that. \$\endgroup\$ – ajs410 Sep 26 '12 at 16:45
7
\$\begingroup\$

Believe it or not, some people actually tried this with Java once. Look up "picoJava" and "Jazelle" on Wikipedia. This is a bit of a different beast, since Java gets compiled to a byte-code that's more like assembly than C, but who knows, this might sort of set you on the right path.

\$\endgroup\$
  • \$\begingroup\$ Haha, funny thing is that I used to write Java :P and I think that this may be the direction we will look at with the most seriousity (cool word, isnt it :) \$\endgroup\$ – fr00ty_l00ps Sep 25 '12 at 17:17
  • 3
    \$\begingroup\$ That's byte-code, which is compiled code, not source code! \$\endgroup\$ – stevenvh Sep 25 '12 at 17:18
  • \$\begingroup\$ Java compiles down to byte-code, true, but it more resembles machine language than assembly language; it runs on a java virtual machine (JVM) that reads byte-code instructions and executes them much like a real processor. So much like a real processor that it has been more than just 'tried', it is feasible to implement a JVM in hardware. Search for 'JOP' for example. \$\endgroup\$ – JustJeff Sep 25 '12 at 17:36
  • 2
    \$\begingroup\$ @JustJeff: Ironically, trying to process that sort of byte code directly will often yield worse performance than using a conventional processor to convert it to conventional-processor machine code and running that. In many cases, the behavior of an instruction may be context-sensitive. A just-in-time compiler may be able to determine that something will always be true of the context in which an instruction executes, and produce compiled machine code which can exploit that; a processor running byte-code directly would be far less able to. \$\endgroup\$ – supercat Sep 25 '12 at 17:52
  • \$\begingroup\$ @supercat - a good point to raise. Also, I have no idea how effectively java bytecode can be treated by a pipeline. And what real processor has the burden of a GC? There's obviously a reason we haven't seen a hardware JVM take off when FPGAs are so inexpensive and ubiquitous. \$\endgroup\$ – JustJeff Sep 25 '12 at 17:59
1
\$\begingroup\$

I'm going to break suit here and answer the question:

No, there is no such processor already on the market, so I would not expect anyone to have a clue about it.

;)

\$\endgroup\$
1
\$\begingroup\$

For a processor to efficiently execute any sort of code, the code must be divisible into relatively small pieces which can be handled independently, with the processor itself maintaining only a minimal amount of state between each piece. Some human-parseable languages (e.g. Forth) may be marginally amenable to such subdivision, and it might be feasible to design a Forth machine that could execute a large ASCII-text program directly from ROM while requiring a relatively small amount of RAM. I don't think such a thing would be remotely possible with C as it is defined (including its macro facility), however, since it may not be possible to determine anything about a program's behavior until the whole thing has been read. Executing an arbitrary C program would require either being able to store an unbounded amount of state, or else requiring an amount of time proportional to the program length in order to perform each operation.

\$\endgroup\$
1
\$\begingroup\$

C was made 40 years ago to be able to be compiled simply, and to generally follow the architecture of typical CPU's. It's original instruction set maps to one or just a few actual CPU codes. But given that, I don't see it as a useful direct to CPU language, just as assembler requires compiling, so will C?

CPUs will over time move closer to the C language constructs. An obvious one to solve is to make a significant change in the number of registers so that they can be mapped 1:1 with variables and not require memory operations all the time. This has been partially solved with pipelines and caches, but this can still be greatly improved

When CPUs ship with a few GB's of internal register storage things will get really interesting! This will also blur the lines between CPU/DSP/FPU/GPU which is where things are heading already!

\$\endgroup\$
-3
\$\begingroup\$

C is a programming language, it needs to be compiled before it can be run on any processor.

\$\endgroup\$
  • 3
    \$\begingroup\$ But assembly is also a programming language and it doesn't need to be compiled to run, only assembled. Machine code, being bijective with assembly, is also programming language and it doesn't even need to be assembled. \$\endgroup\$ – AndrejaKo Sep 25 '12 at 16:54
  • 3
    \$\begingroup\$ Technically, C can be interpreted. But that is just being pedantic and doesn't help these guys make a CPU. \$\endgroup\$ – user3624 Sep 25 '12 at 16:56
  • \$\begingroup\$ Wait, C can be interpreted? Like RUBY???? :) \$\endgroup\$ – fr00ty_l00ps Sep 25 '12 at 17:07
  • \$\begingroup\$ @CodeAdmiral Did you even read the C Wikipedia article? What you're considering is SERIOUS BUSINESS™ and requires serious research and experience. \$\endgroup\$ – AndrejaKo Sep 25 '12 at 17:51
  • 4
    \$\begingroup\$ No, C doesn't need to be compiled into machine code and then run. That is how it's done because it greatly reduces hardware complexity, but it is not strictly speaking necessary. \$\endgroup\$ – Olin Lathrop Sep 25 '12 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.