Research topic in computer science

[Light Space]

Hi all, i am an M.Tech student in computer science & eng. I have to do project as part of course.

And also i have to submit a seminar. The problem is i was asked to find a ieee or acm or another

international journal paper as seminar and improve that paper with something new of my own

to create my project and some papers.

 

How do i know i can do some paper found on ieee or international journal.

 

I am particularly interested in device driver and kernel programming. is there any research papers on that.

[Enthalpy]

I don't know if this is what you're looking for... Not published in ieee nor acm as far as I know.

I had put it there and elsewhere, but it has disappeared for some reason:

http://www.msfn.org/board/index.php?showtopic=129474

I'll have to give a look.

 

Anyway, it's easy enough that you can put the first hard thoughts on it without previous research papers. And at least it should be original.

 

I imagine executable programmes can be compressed on hard disk drives, Ram and maybe L2 cache, so these all get a better throughput. Not a huge and complicated compression: just something fast hardware can expand without time penalty, on the Cpu chip. Even if you gain 30% code size, this means money: you can have 2 banks of Ram instead of 3 for instance. And 64b programmes need compression more badly because they're more redundent than 32b programmes.

 

Some readers had understood it wrongly in the past, so let me explain it again:

I don't want extra instructions that improve the speed of zip expansion. I don't want software that expands the executable programme.

I want standalone hardware (hard-wired or nearly) that expands the programme on-the-fly during transfers from the Ram to the slowest cache, or even later, between the caches.

This puts strong limitations on the nature of the compression, which I suppose must still be invented, in direct connection with said hardware.

 

Marc Schaefer, aka Enthalpy

[Light Space]

Thanks bro, i am curious.

If such is the case of limitation, how would you explain the compression?.

 

Say the system is RISC and all the instructions are constant length instructions, say 16bits (2bytes).

We can think of compression like this. We won't have enough instructions to be represented by 16bit

for particular CPU. I.e. we don't have 2^16 instructions. Say we have only 128 instructions for instruction set. this could

easily be encoded by just 7bits. We could think of a decoding hardware that convert this to actual 16bit before

being consumed by CPU.

[Enthalpy]

That's the fundamental idea, yes. Then, you can add subtleties:

 

- Long jumps exist, and because the executable code contains addresses and other information whose compression has a different efficiency as the instructions, you need some method to predict which page of the compressed executable contains the sought address. A table of addresses where each page begins? A table of jump addresses? (Difficult with computed jumps)

 

- The real goal, but difficult, is x64 code - nearly 100% of the Cpu market soon, and about the rest is i386 anyway. i386 code is highly irregular because of history, x64 may be easier. Risc is better but hasn't taken the market, alas, so forget this theoretical possibility.

 

- You have to compress addresses as well since these make a good proportion of x64 code. They waste 64 bits despite programmes and data need less, so something like identifying a few segments and recoding as relative addresses should save a lot. Check if dynamic addresses can be created. Mind the paging mechanism. Use associative memory if needed.

 

- Among the 128 instructions you give as an example, some are more frequent and should have a shorter code - this is known compression theory. Other compression methods identify data that frequently belongs together, say Decrement then Compare followed by Branch, and replace the group with a shorter code. Though, wired off-the-fly hardware limits the achieveable subtlety of compression.

 

- But the no-execute bit (since Amd64, P4, Windows Xp) tells you which page contains data or programme, relieve.

 

Two extreme approach would involve:

- Use a known compression method (Lzma...) not specialized in programmes, see how to hardwire it; probably inefficient.

- Take the i64 instruction set, decide by hand how to compact it.

The intermediate method would let a compressor run on a few i64 programmes, and then you check by hand what you keep or not, freeze it and hardwire it.

 

UPX is a software decompressor (and compressor) meant for executables

http://upx.sourceforge.net/

if it could be hardwired as is, this would be the answer, but I've no idea if this is possible. Or, simplify it until hardware expands on-the-fly. This looks like the first-choice approach, because software decoding by Upx already improves the performance of computers with slow disks. And people at sourceforge may be helpful.

 

To be clear: as a software, UPX loads compressed executable from the disk in the Ram and expands it in the Ram, so it saves no Ram throughput nor size. The hardware expander I imagine keeps the executable compressed in the Ram and maybe L3 cache and expands it in the Cpu, to save Ram throughput and size. Expansion would be between Ram and L3 or between L3 and L2. Beware that in L1 cache, the code is transformed into micro-op and macro-op since the P4, still a different story, so I'd keep my fingers away from L1.

 

Such engineering details make the project less obvious than it first seems - but hey, you must deserve your diploma! And the implications are big, as Ram throughput makes much of the difference between a socket 1155 and a socket 2011. Think as well at Ram size, disk throughput, disk size...

 

Fun? At least to my taste, yes.

Marc Schaefer, aka Enthalpy

Edited August 17, 2012 by Enthalpy